On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary

DOI10.1007/S00493-009-2407-4MaRDI QIDQ2149491zbMATH OpenOpenAlexFDO

Authors Werner Schwärzler

Publication date 29 June 2022

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-009-2407-4

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Recommendations

• On the complexity of the planar directed edge-disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the edge-disjoint min-min problem in planar digraphs
• On the complexity of the disjoint paths problem
• Maximum Edge-Disjoint Paths Problem in Planar Graphs

Cites work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge-disjoint paths in planar graphs
• Multicommodity flows in planar graphs
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the disjoint paths problem

Cited in

(11)

• Linkage on the infinite grid
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the planar directed edge-disjoint paths problem
• A tight lower bound for edge-disjoint paths on planar DAGs
• scientific article; zbMATH DE number 4202293 (Why is no real title available?)
• The complexity of the edge disjoint multiple paths problem when constructed over uniformly directed mesh graphs
• Shortest k-disjoint paths via determinants
• On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• The hardness of routing two pairs on one face
• Multiflows in symmetric digraphs

This page was built for publication: On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary

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