TCS-TR-A-14-75Date: Thu Jul 17 15:18:55 2014 Title: An Efficient Method of Indexing All Topological Orders for a Given DAG Authors: Yuma Inoue and Shin-ichi Minato Contact:
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 DD, which generates and indexes a set of permutations. In this paper, we propose Rot-DDs, which are a variation of DDs based on a different interpretation. Compression ratios of Rot-DDs for representing topological orders are theoretically improved from the original DDs. We propose an efficient method for constructing a Rot-DD based on dynamic programming approach. Computational experiments show the amazing efficiency of a Rot-DD: a Rot-DD for 3.7x10^{41} topological orders has only 2.2x10^7 nodes and is constructed in 36 seconds. In addition, the indexed structure of a Rot-DD allows us to fast post-process such as edge addition and random samplings. ©Copyright 2014 Authors |