scientific article; zbMATH DE number 1303036

zbMATH Open0947.68078MaRDI QIDQ4249537FDOQ4249537

Authors: Xiao Zhou, Takao Nishizeki 

Publication date: 6 November 2000

Title of this publication is not available (Why is that?)

Recommendations

• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Finding edge-disjoint paths in partial k-trees
• Finding edge-disjoint paths in partial \(k\)-trees
• NP-completeness of some edge-disjoint paths problems

zbMATH Keywords

combinatorial problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (7)

• The complexity of path coloring and call scheduling
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Length 3 edge-disjoint paths is NP-hard
• On the complexity of the regenerator location problem treewidth and other parameters
• Finding edge-disjoint paths in partial k-trees
• Finding edge-disjoint paths in partial \(k\)-trees
• Eulerian disjoint paths problem in grid graphs is NP-complete

This page was built for publication:

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