Edge Disjoint Paths in Moderately Connected Graphs

DOI10.1137/080715093MaRDI QIDQ5893911zbMATH OpenOpenAlexFDO

Authors

Publication date 4 November 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/704cc4af51ffc75a6528a0474aeb937a5dc61342

zbMATH Keywords

edge disjoint pathspolylogarithmic approximationrandom sampling in cutsundirected graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Edge Disjoint Paths in Moderately Connected Graphs
• scientific article; zbMATH DE number 2079393
• Edge-disjoint paths revisited
• Edge-disjoint paths in planar graphs
• Edge-disjoint paths and cycles inn-edge-connected graphs
• Edge-disjoint paths in digraphs with bounded independence number
• scientific article; zbMATH DE number 4089593
• scientific article; zbMATH DE number 1445370
• Edge-disjoint paths in expander graphs
• scientific article; zbMATH DE number 1555936

Cited in

(13)

• New algorithms for maximum disjoint paths based on tree-likeness
• The power of cut-based parameters for computing edge disjoint paths
• The power of cut-based parameters for computing edge-disjoint paths
• Routing in undirected graphs with constant congestion
• New hardness results for routing on disjoint paths
• Minimum-cost network design with (dis)economies of scale
• scientific article; zbMATH DE number 5530160 (Why is no real title available?)
• Constant congestion routing of symmetric demands in planar directed graphs
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Almost polynomial hardness of node-disjoint paths in grids
• Hallucination helps: energy efficient virtual circuit routing
• A general framework for graph sparsification
• Edge Disjoint Paths in Moderately Connected Graphs

This page was built for publication: Edge Disjoint Paths in Moderately Connected Graphs

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