The Community for Technology Leaders
RSS Icon
Subscribe
Zurich, Switzerland
July 4, 2007 to July 6, 2007
ISBN: 0-7695-2907-0
pp: 765-770
Yangjun Chen , University of Winnipeg
ABSTRACT
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.
INDEX TERMS
null
CITATION
Yangjun Chen, "Tree Encoding and Transitive Closure Compression", IV, 2007, 2013 17th International Conference on Information Visualisation, 2013 17th International Conference on Information Visualisation 2007, pp. 765-770, doi:10.1109/IV.2007.116
29 ms
(Ver 2.0)

Marketing Automation Platform Marketing Automation Tool