The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
type: Item
instance of: scholarly article
title: The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
zbMATH Open document ID: 1374.05137
author: Ken-ichi Kawarabayashi
author: Yusuke Kobayashi
published in: Combinatorica
publication date: 2017-03-31T00:00:00Z
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 6699286
zbMATH Keywords: edge-disjoint paths
zbMATH Keywords: \(4\)-edge-connected graphs
zbMATH Keywords: Eulerian graphs
MaRDI profile type: Publication
full work available at URL: s00493-014-2828-6
OpenAlex ID: W3136471880
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Edge-Disjoint Paths in Planar Graphs with Constant Congestion
cites work: Graph Drawing
cites work: Linearity of grid minors in treewidth with applications through bidimensionality
cites work: Highly connected sets and the excluded grid theorem
cites work: Q3972951
cites work: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
cites work: S-functions for graphs
cites work: The NP-completeness column: An ongoing guide
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Q5417629
cites work: The disjoint paths problem in quadratic time
cites work: A shorter proof of the graph minor algorithm: the unique linkage theorem
cites work: Q4231910
cites work: Q4234048
cites work: On the complexity of the disjoint paths problem
cites work: A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
cites work: The edge-disjoint paths problem is NP-complete for series-parallel graphs
cites work: Multicommodity flows in planar graphs
cites work: AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
cites work: Q4352948
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. V. Excluding a planar graph
cites work: Q3972953
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. XXI. graphs with unique linkages
cites work: Graph minors. XXII. Irrelevant vertices in linkage problems
cites work: Quickly excluding a planar graph
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Disjoint paths in graphs
cites work: On Odd Cuts and Plane Multicommodity Flows
cites work: 2-linked graphs
cites work: A simpler proof of the excluded minor theorem for higher surfaces
DOI: 10.1007/S00493-014-2828-6
description: scientific article; zbMATH DE number 6699286