The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
From MaRDI portal
Publication:520046
DOI10.1007/s00493-014-2828-6zbMath1374.05137OpenAlexW3136471880MaRDI QIDQ520046
Yusuke Kobayashi, Ken-ichi Kawarabayashi
Publication date: 31 March 2017
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00493-014-2828-6
Paths and cycles (05C38) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)
Related Items
Edge-disjoint odd cycles in 4-edge-connected graphs, Coloring immersion-free graphs, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The disjoint paths problem in quadratic time
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Linearity of grid minors in treewidth with applications through bidimensionality
- Graph minors. XXI. graphs with unique linkages
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Disjoint paths in graphs
- 2-linked graphs
- Multicommodity flows in planar graphs
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- S-functions for graphs
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- A simpler proof of the excluded minor theorem for higher surfaces
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Graph minors. XIII: The disjoint paths problem
- On the complexity of the disjoint paths problem
- A shorter proof of the graph minor algorithm
- Graph minors. II. Algorithmic aspects of tree-width
- On Odd Cuts and Plane Multicommodity Flows
- On the Computational Complexity of Combinatorial Problems
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph Drawing
- The NP-completeness column: An ongoing guide
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
