This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
11th International Conference Information Visualization (IV '07)
Tree Encoding and Transitive Closure Compression
Zurich, Switzerland
July 04-July 06
ISBN: 0-7695-2900-3
Yangjun Chen, University of Winnipeg
Tree encoding is a very useful mechanism to check ancestordescendant relationships of the nodes in a tree structure, by which each node is associated with a pair of integers that can be used to characterize the reachability. Recently, this method is extended to directed graphs (digraph for short) G by associating each node in G with a pair sequence. However, no approach is reported to minimize such pair sequences. In this paper, we address this issue and propose an efficient algorithm that is always able to generate minimized pair sequences. The algorithm runs in O(b?e + b?n? ) time and O(b?n), where n and e are the numbers of the nodes and edges of a DAG, respectively; and b is the DAG?s width.
Citation:
Yangjun Chen, "Tree Encoding and Transitive Closure Compression," iv, pp.765-770, 11th International Conference Information Visualization (IV '07), 2007
Usage of this product signifies your acceptance of the Terms of Use.