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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Linkage on the infinite grid
• Multiflows in symmetric digraphs
• Title not available (Why is that?)
• 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
• 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)