The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
From MaRDI portal
Publication:520046
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
Cites work
- scientific article; zbMATH DE number 16298 (Why is no real title available?)
- scientific article; zbMATH DE number 16300 (Why is no real title available?)
- scientific article; zbMATH DE number 1261807 (Why is no real title available?)
- scientific article; zbMATH DE number 1263178 (Why is no real title available?)
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- 2-linked graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A shorter proof of the graph minor algorithm: the unique linkage theorem
- A simpler proof of the excluded minor theorem for higher surfaces
- An improved algorithm for finding tree decompositions of small width
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Disjoint paths in graphs
- Edge-disjoint paths in planar graphs with constant congestion
- Graph Drawing
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. V. Excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XXI. graphs with unique linkages
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Highly connected sets and the excluded grid theorem
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Linearity of grid minors in treewidth with applications through bidimensionality
- Multicommodity flows in planar graphs
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
- On Odd Cuts and Plane Multicommodity Flows
- On the Computational Complexity of Combinatorial Problems
- On the complexity of the disjoint paths problem
- Quickly excluding a planar graph
- S-functions for graphs
- The NP-completeness column: An ongoing guide
- The disjoint paths problem in quadratic time
- The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
Cited in
(9)- Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs
- 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
- Coloring immersion-free graphs
- An \(O(\log n)\)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar 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
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)
