This Article 
 Bibliographic References 
 Add to: 
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.
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.