Paper Info
Title
An Efficient Method for Indexing All Topological Orders of a Directed Graph.
Abstract
Topological orders of a directed graph are an important concept of graph algorithms. The generation of topological orders is useful for designing graph algorithms and solving scheduling problems. In this paper, we generate and index all topological orders of a given graph. Since topological orders are permutations of vertices, we can use the data structure pi DD, which generates and indexes a set of permutations. In this paper, we propose Rot-pi DDs, which are a variation of pi DDs based on a different interpretation. Compression ratios of Rot-pi DDs for representing topological orders are theoretically improved from the original pi DDs. We propose an efficient method for constructing a Rot-pi DD based on dynamic programming approach. Computational experiments show the amazing efficiencies of a Rot-pi DD: a Rot-pi DD for 3.7 x 10(41) topological orders has only 2.2 x 10(7) nodes and is constructed in 36 seconds. In addition, the indexed structure of a Rot-pi DD allows us to fast post-process operations such as edge addition and random samplings.
Year
DOI
Venue
2014
10.1007/978-3-319-13075-0_9
ALGORITHMS AND COMPUTATION, ISAAC 2014
Keywords
Field
DocType
Topological orders,Linear extensions,Permutations,Decision diagrams,Enumerating algorithms,Experimental algorithms
Discrete mathematics,Topology,Combinatorics,Comparability graph,Graph property,Computer science,Graph embedding,Null graph,Topological graph theory,Feedback arc set,Voltage graph,Complement graph
Conference
Volume
ISSN
Citations 
8889
0302-9743
2
PageRank 
References 
Authors
0.38
10
2
Name
Order
Citations
PageRank
Yuma Inoue132.44
Shin-ichi Minato272584.72