The Vertex-Disjoint Menger Problem in Planar Graphs

DOI10.1137/S0097539793253565zbMATH Open0869.05059OpenAlexW1976957234MaRDI QIDQ4337639FDOQ4337639

Authors Heike Ripphausen-Lipa, Dorothea Wagner, Karsten Weihe

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539793253565

zbMATH Keywords

graph algorithmsplanar graphsdisjoint paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 437535
• Maximum Edge-Disjoint Paths Problem in Planar Graphs
• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• On shortest disjoint paths in planar graphs
• On shortest disjoint paths in planar graphs
• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs (extended abstract)
• Edge-disjoint maximal planar graphs
• The Maximum Independent Set Problem in Planar Graphs
• Irrelevant vertices for the planar disjoint paths problem

Cited in

(19)

• scientific article; zbMATH DE number 437535 (Why is no real title available?)
• Vertex disjoint paths in upward planar graphs
• Irrelevant vertices for the planar disjoint paths problem
• Vertex disjoint paths for dispatching in railways
• A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
• Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph
• A linear time algorithm for the arc disjoint Menger problem in planar directed graphs (extended abstract)
• scientific article; zbMATH DE number 780786 (Why is no real title available?)
• A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works
• Interdiction problems on planar graphs
• scientific article; zbMATH DE number 833804 (Why is no real title available?)
• Visibility representations of toroidal and Klein-bottle graphs
• Efficient algorithms for listing \(k\) disjoint \(st\)-paths in graphs
• Extending convex partial drawings of graphs
• Towards single face shortest vertex-disjoint paths in undirected planar graphs
• Untangling planar graphs from a specified vertex position-Hard cases
• Maximum flow in directed planar graphs with vertex capacities
• Finding edge-disjoint paths in networks: an ant colony optimization algorithm
• Computing vertex-disjoint paths in large graphs using MAOs

This page was built for publication: The Vertex-Disjoint Menger Problem in Planar Graphs

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