A linear time algorithm for the arc disjoint Menger problem in planar directed graphs (extended abstract)

DOI10.1007/3-540-63397-9_6zbMATH Open1477.68207OpenAlexW2052412003MaRDI QIDQ826071FDOQ826071

Authors: Ulrik Brandes, Dorothea Wagner 

Publication date: 20 December 2021

Full work available at URL: https://doi.org/10.1007/3-540-63397-9_6

Recommendations

• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
• A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
• The Vertex-Disjoint Menger Problem in Planar Graphs
• scientific article; zbMATH DE number 437535
• A linear-time algorithm for edge-disjoint paths in planar graphs

zbMATH Keywords

disjoint pathplanar graphlinear-time algorithmsearch pathsearch step

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Cited In (3)

• The Vertex-Disjoint Menger Problem in Planar Graphs
• An efficient computation of the rank function of a positroid
• A linear programming formulation of Mader's edge-disjoint paths problem

This page was built for publication: A linear time algorithm for the arc disjoint Menger problem in planar directed graphs (extended abstract)

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