Length 3 edge-disjoint paths is NP-hard
From MaRDI portal
Publication:445249
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
NP-completenessdirected graphoriented graphNP-hardnessnetwork flowdegree sequenceEdge-disjoint paths
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Vertex degrees (05C07)
Related Items
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