The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

DOI10.1007/S00493-014-2828-6zbMATH Open1374.05137OpenAlexW3136471880MaRDI QIDQ520046FDOQ520046

Authors: Ken-ichi Kawarabayashi, Yusuke Kobayashi 

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

Recommendations

• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs
• An \(O(\log n)\)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
• On the complexity of the disjoint paths problem
• Edge Disjoint Paths in Moderately Connected Graphs

zbMATH Keywords

edge-disjoint pathsEulerian graphs\(4\)-edge-connected graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40) Graph minors (05C83)

Cites Work

• Title not available (Why is that?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• 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
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• A shorter proof of the graph minor algorithm: the unique linkage theorem
• Graph minors. II. Algorithmic aspects of tree-width
• Title not available (Why is that?)
• Title not available (Why is that?)
• The disjoint paths problem in quadratic time
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• On the complexity of the disjoint paths problem
• On Odd Cuts and Plane Multicommodity Flows
• On the Computational Complexity of Combinatorial Problems
• S-functions for graphs
• Graph minors. XXI. graphs with unique linkages
• Graph minors. XXII. Irrelevant vertices in linkage problems
• An improved algorithm for finding tree decompositions of small width
• Linearity of grid minors in treewidth with applications through bidimensionality
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Title not available (Why is that?)
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Multicommodity flows in planar graphs
• A simpler proof of the excluded minor theorem for higher surfaces
• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Title not available (Why is that?)
• Edge-disjoint paths in planar graphs with constant congestion
• Graph Drawing
• The NP-completeness column: An ongoing guide

Cited In (9)

• Edge-disjoint odd cycles in 4-edge-connected graphs
• An \(O(\log n)\)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
• An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs
• Coloring immersion-free graphs
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• A linear time algorithm for finding three edge-disjoint paths in Eulerian networks
• The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs

This page was built for publication: The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs

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