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

DOI10.1007/S00493-009-2407-4OpenAlexW2030101236MaRDI QIDQ2149491FDOQ2149491

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 (10)

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

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)