All-Pairs Ancestor Problems in Weighted Dags

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BAUMGART, Matthias, Stefan ECKHARDT, Jan GRIEBSCH, Sven KOSUB, Johannes NOWAK, 2007. All-Pairs Ancestor Problems in Weighted Dags. International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : ESCAPE 2007. Hangzhou, China, Apr 7, 2007 - Apr 9, 2007. In: CHEN, Bo, ed., Mike PATERSON, ed., Guochuan ZHANG, ed.. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : Revised Selected Papers. Berlin:Springer, pp. 282-293. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-74449-8. Available under: doi: 10.1007/978-3-540-74450-4_26

@inproceedings{Baumgart2007AllPa-44936, title={All-Pairs Ancestor Problems in Weighted Dags}, year={2007}, doi={10.1007/978-3-540-74450-4_26}, number={4614}, isbn={978-3-540-74449-8}, issn={0302-9743}, address={Berlin}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : Revised Selected Papers}, pages={282--293}, editor={Chen, Bo and Paterson, Mike and Zhang, Guochuan}, author={Baumgart, Matthias and Eckhardt, Stefan and Griebsch, Jan and Kosub, Sven and Nowak, Johannes} }

Griebsch, Jan Kosub, Sven Baumgart, Matthias Nowak, Johannes 2019-02-08T13:19:05Z Eckhardt, Stefan This work studies (lowest) common ancestor problems in (weighted) directed acyclic graphs. We improve previous algorithms for the all-pairs representative LCA problem to O(n <sup>2.575</sup>) by using fast rectangular matrix multiplication. We prove a first non-trivial upper bound of O( min {n <sup>2</sup> m, n <sup>3.575</sup> }) for the all-pairs all lowest common ancestors problem. Furthermore, classes of dags are identified for which the problem can be solved considerably faster. Our algorithms scale with the maximal number of LCAs for one pair and—based on the famous Dilworth’s theorem—with the size of a maximum antichain (i.e., width) of the dag. We extend and generalize previous results on computing shortest ancestral distances. It is shown that finding shortest distance common ancestors in weighted dags is not harder than computing all-pairs shortest distances, up to a polylogarithmic factor. Finally, we present a solution for the general all-pairs shortest distance LCA problem based on computing all-pairs all LCAs. All-Pairs Ancestor Problems in Weighted Dags Kosub, Sven Eckhardt, Stefan Griebsch, Jan 2019-02-08T13:19:05Z Nowak, Johannes eng Baumgart, Matthias 2007

This item appears in the following Collection(s)

Search KOPS


Browse

My Account