Edge Disjoint Paths in Moderately Connected Graphs

DOI10.1137/080715093zbMath1207.68448OpenAlexW2019041817MaRDI QIDQ5893911

No author found.

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

undirected graphsedge disjoint pathspolylogarithmic approximationrandom sampling in cuts

Mathematics Subject Classification ID

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

Related Items (9)

Minimum-Cost Network Design with (Dis)economies of Scale ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Unnamed Item ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Hallucination Helps: Energy Efficient Virtual Circuit Routing ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ A General Framework for Graph Sparsification ⋮ Unnamed Item

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