Abstract
We develop a path cover technique to solve lowest common ancestor (LCA for short) problems in a directed acyclic graph (dag).
Our method yields improved upper bounds for two recently studied problem variants, computing one (representative) LCA for all pairs of vertices and computing all LCAs for all pairs of vertices. The bounds are expressed in terms of the number n of vertices and the so called width w(G) of the input dag G. For the first problem we achieve \(\widetilde{O}(n^2 w(G))\) time which improves the upper bound of [18] for dags with w(G) = O( n 0.376 − δ) for a constant δ> 0. For the second problem our \(\widetilde{O}(n^2 w(G)^2)\) upper time bound subsumes the O(n 3.334) bound established in [11] for w(G) = O(n 0.667 − δ).
As a second major result we show how to combine the path cover technique with LCA solutions for dags with small depth [9]. Our algorithm attains the best known upper time bound for this problem of O(n 2.575). However, most notably, the algorithm performs better on a vast amount of input dags, i.e. dags that do not have an almost linear-sized subdag of extremely regular structure.
Finally, we apply our technique to improve the general upper time bounds on the worst case time complexity for the problem of reporting LCAs for each triple of vertices recently established by Yuster[26].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aït-Kaci, H., Boyer, R., Lincoln, P., Nasr, R.: Efficient Implementation of Lattice Operations. ACM Transactions on Programming Languages 11(1), 115–146 (1989)
Aho, A., Hopcroft, J., Ullman, J.: On Finding Lowest Common Ancestors in Trees. SIAM Journal on Computing 5(1), 115–132 (1976)
Barak, A., Erdös, P.: On the maximal number of strongly independent vertices in a random acyclic directed graph. SIAM J. Algebraic Discrete Methods 5, 508–514 (1984)
Baumgart, M., Eckhardt, S., Griebsch, J., Kosub, S., Nowak, J.: All-Pairs Common Ancestor Problems in Weighted Directed Acyclic Graphs. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol. 4614, pp. 282–293. Springer, Heidelberg (2007)
Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. Journal of Algorithms 57(2), 75–94 (2005); A preliminary version. In: Proc. SODA 2001, pp. 845–853 (2001)
Coppersmith, D.: Rectangular matrix multiplication revisited. Journal of Symbolic Computation 13, 42–49 (1997)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progression. Journal of Symbolic Computation 9, 251–290 (1990)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill Book Company, Boston (2001)
Czumaj, A., Kowaluk, M., Lingas, A.: Faster algorithms for finding lowest common ancestors in directed acyclic graphs. In: The special ICALP 2005, Theoretical Computer Science, vol. 380(1-2), pp. 37–46 (2007)
Dilworth, R.: A decomposition theorem for partially ordered sets. Annals of Mathematics 51(1), 161–166 (1950)
Eckhardt, S., Mühling, A., Nowak, J.: Fast Lowest Common Ancestor Computations in Dags. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 705–716. Springer, Heidelberg (2007)
Felsner, S., Raghavan, V., Spinrad, J.: Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number. Order 20(4), 351–364 (2003)
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2), 338–355 (1984)
Hopcroft, J.E., Karp, R.M.: An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J.Comput. 2(4), 225–231 (1973)
Huang, X., Pan, V.Y.: Fast rectangular matrix multiplications and applications. Journal of Complexity 14, 257–299 (1998)
Kowaluk, M., Lingas, A.: LCA queries in directed acyclic graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 241–248. Springer, Heidelberg (2005)
Kowaluk, M., Lingas, A.: Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 265–274. Springer, Heidelberg (2007)
Kowaluk, M., Lingas, A., Nowak, J.: A Path Cover Technique for LCAs in Dags. Technical Report TUM-I0809, Technische Universität München (2008)
Mucha, M., Sankowski, P.: Maximum Matchings via Gaussian Elimination. In: Proc. FOCS 2004, pp. 248–255 (2004)
Nykänen, M., Ukkonen, E.: Finding lowest common ancestors in arbitrarily directed trees. Information Processing Letters 50(6), 307–310 (1994)
Schieber, B., Vishkin, U.: On Finding Lowest Common Ancestors: Simplification and Parallelization. SIAM Journal on Computing 17(6), 1253–1262 (1988)
Shäffer, A.A., Gupta, S.K., Shriram, K., Cottingham Jr., R.W.: Avoiding recomputation in linkage analysis. Human Heredity 44, 225–237 (1994)
Simon, K.: An Improved Algorithm for Transitive Closure on Acyclic Digraphs. Theor. Comput. Sci. 58, 325–346 (1988)
Tarjan, R.E.: Applications of path compression on balanced trees. Journal of the ACM 26(4), 690–715 (1979)
Yuster, R.: All-pairs disjoint paths from a common ancestor in \(\widetilde{O}(n^{\omega})\) time. Theoretical Computer Science 396(1-3), 145–150 (2008)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kowaluk, M., Lingas, A., Nowak, J. (2008). A Path Cover Technique for LCAs in Dags. In: Gudmundsson, J. (eds) Algorithm Theory – SWAT 2008. SWAT 2008. Lecture Notes in Computer Science, vol 5124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69903-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-69903-3_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69900-2
Online ISBN: 978-3-540-69903-3
eBook Packages: Computer ScienceComputer Science (R0)