scientific article; zbMATH DE number 1303036

MaRDI QIDQ4249537zbMATH OpenFDO

Authors Xiao Zhou, Takao Nishizeki

Publication date 6 November 2000

zbMATH Keywords

combinatorial problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cited in

(7)

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

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)