Length 3 edge-disjoint paths is NP-hard

DOI10.1007/s00037-012-0038-4zbMath1247.05118arXiv1201.6578OpenAlexW2075741721MaRDI QIDQ445249

Jennifer Iglesias, Hannah Alpert

Publication date: 24 August 2012

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.6578

zbMATH Keywords

NP-completenessdirected graphoriented graphNP-hardnessnetwork flowdegree sequenceEdge-disjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Vertex degrees (05C07)

Related Items (2)

Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs ⋮ Length 3 edge-disjoint paths is NP-hard

Cites Work

• Length 3 edge-disjoint paths is NP-hard
• On the complexity of vertex-disjoint length-restricted path problems

This page was built for publication: Length 3 edge-disjoint paths is NP-hard