Algorithms for junctions in acyclic digraphs

DOI10.1007/978-3-642-38189-8_8MaRDI QIDQ5265169zbMATH OpenOpenAlexFDO

Authors Álvaro J. P. Franco, Carlos E. Ferreira

Publication date 22 July 2015

Published in Facets of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38189-8_8

zbMATH Keywords

genealogypath problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90)

Recommendations

• Disjoint paths in acyclic digraphs
• All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time
• scientific article; zbMATH DE number 1498519
• A \(\min\)-\(\max\) relation in flowgraphs and some applications
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs

Cited in

(3)

• A \(\min\)-\(\max\) relation in flowgraphs and some applications
• A min-max relation in flowgraphs
• Lifted Dynamic Junction Tree Algorithm

This page was built for publication: Algorithms for junctions in acyclic digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5265169)