Abstract
In this paper, we propose an efficient algorithm to decompose a directed acyclic graph (DAG) into chains, which has a lot of applications in computer science and engineering. Especially, it can be used to store transitive closures of directed graphs in an economical way. For a DAG G with n nodes, our algorithm needs O\((n^{2} + bn \sqrt{b} )\) time to find a minimized set of disjoint chains, where b is G′s width, defined to be the largest node subset U of G such that for every pair of nodes u, v ∈̣U, there does not exist a path from u to v or from v to u. Accordingly, the transitive closure of G can be stored in O(bn) space, and the reachability can be checked in O(logb) time. The method can also be extended to handle cyclic directed graphs.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alt, H., Blum, N., Mehlhorn, K., Paul, M.: Computing a maximum cardinality matching in a bipartite graph in time O(n1.5 \(\sqrt{e/(logn)}\)). Information Processing Letters 37, 237–240 (1991)
Asratian, A.S., Denley, T., Haggkvist, R.: Bipartite Graphs and their Applications, Cambridge University (1998)
Banerjee, J., Kim, W., Kim, S., Garza, J.F.: Clustering a DAG for CAD Databases. IEEE Trans. on Knowledge and Data Engineering 14(11), 1684–1699 (1988)
Chen, Y., Cooke, D.: On the Transitive Closure Representation and Adjustable Compression. In: SAC 2006, April 23-27, Dijon, France, pp. 450–455 (2006)
Hopcroft, J.E., Karp, R.M.: An n2.5 algorithm for maximum matching in bipartite graphs. SIAM J. Comput. 2, 225–231 (1973)
Jagadish, H.V.: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Systems 15(4), 558–598 (1990)
Keller, T., Graefe, G., Maier, D.: Efficient Assembly of Complex Objects. In: Proc. ACM SIGMOD conf. Denver, Colo., pp. 148–157 (1991)
Kuno, H.A., Rundensteiner, E.A.: Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation. IEEE Transactions on Knowledge and Data Engineering 10(5), 768–792 (1998)
Teuhola, J.: Path Signatures: A Way to Speed up Recursion in Relational Databases. IEEE Trans. on Knowledge and Data Engineering 8(3), 446–454 (1996)
Wang, H., Meng, X.: On the Sequencing of Tree Structures for XML Indexing. In: Proc. Conf. Data Engineering, Tokyo, Japan, pp. 372–385 (April 2005)
Zhang, C., Naughton, J., DeWitt, D., Luo, Q., Lohman, G.: On Supporting Containment Queries in Relational Database Management Systems. In: Proc. of ACM SIGMOD Intl. Conf. on Management of Data, California (2001)
Zibin, Y., Gil, J.: Efficient Subtyping Tests with PQ-Encoding. In: Proc. of the 2001 ACM SIGPLAN conf. on Object-Oriented Programming Systems, Languages and Application, Florida, pp. 96–107 (October 14-18, 2001)
Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51, 161–166 (1950)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, Y. (2007). Decomposing DAGs into Disjoint Chains. In: Wagner, R., Revell, N., Pernul, G. (eds) Database and Expert Systems Applications. DEXA 2007. Lecture Notes in Computer Science, vol 4653. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74469-6_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-74469-6_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74467-2
Online ISBN: 978-3-540-74469-6
eBook Packages: Computer ScienceComputer Science (R0)