scientific article; zbMATH DE number 16300

MaRDI QIDQ3972953zbMATHFDO

Authors Neil Robertson, Paul Seymour

Publication date 26 June 1992

zbMATH Keywords

NP-completepolynomial algorithmtree-widthminorsdisjoint paths algorithmirrelevant vertex

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Recommendations

• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 727422
• Disjoint Paths—A Survey
• The disjoint paths problem in quadratic time
• Graph minors. II. Algorithmic aspects of tree-width

Cited in

(37)

• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• scientific article; zbMATH DE number 3858436 (Why is no real title available?)
• Graph minors. II. Algorithmic aspects of tree-width
• Routing in undirected graphs with constant congestion
• On the complexity of the bilevel minimum spanning tree problem
• Edge-disjoint odd cycles in 4-edge-connected graphs
• General vertex disjoint paths in series-parallel graphs
• The disjoint paths problem in quadratic time
• Single-Sink Multicommodity Flow with Side Constraints
• Algorithms and obstructions for linear-width and related search parameters
• A note on multiflows and treewidth
• Two disjoint negative cycles in a signed graph
• \(K_{a,k}\) minors in graphs of bounded tree-width
• Searching for \(f\)-Hamiltonian circuits
• Combing a Linkage in an Annulus
• Tight bounds for linkages in planar graphs
• Disjoint Paths—A Survey
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Redundant multicast routing in multilayer networks with shared risk resource groups: complexity, models and algorithms
• Graph minors. XXII. Irrelevant vertices in linkage problems
• The Directed Disjoint Shortest Paths Problem
• On the computational complexity of closest genome problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Some recent progress and applications in graph minor theory
• Kernelization of two path searching problems on split graphs
• Finding disjoint paths with related path costs
• Elimination of local bridges
• On the kernelization of split graph problems
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
• New hardness results for routing on disjoint paths
• On shortest disjoint paths in planar graphs
• Mengerian graphs: characterization and recognition
• Subexponential parameterized algorithms
• The extremal function for 3-linked graphs
• A lower bound on the tree-width of graphs with irrelevant vertices
• Improved approximation for node-disjoint paths in grids with sources on the boundary

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 Q3972953)