scientific article

DOI10.4086/toc.2006.v002a007zbMath1213.68700OpenAlexW2140262267MaRDI QIDQ3002769

Chandra Chekuri, F. Bruce Shepherd, Sanjeev Khanna

Publication date: 24 May 2011

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2006.v002a007

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximation algorithmroutingdirected acyclic graphsundirected graphsintegrality gapunsplittable flowedge disjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Paths and cycles (05C38) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

A note on multiflows and treewidth ⋮ Medial Axis Based Routing Has Constant Load Balancing Factor ⋮ The maximum integer multiterminal flow problem in directed graphs ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Unnamed Item ⋮ Finding multiple induced disjoint paths in general graphs ⋮ Tree metrics and edge-disjoint \(S\)-paths ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Approximability of Packing Disjoint Cycles ⋮ Stochastic Unsplittable Flows ⋮ Approximability of packing disjoint cycles ⋮ Disjoint paths in sparse graphs ⋮ Maximum bipartite flow in networks with adaptive channel width ⋮ Routing with congestion in acyclic digraphs ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Unnamed Item ⋮ A logarithmic approximation for unsplittable flow on line graphs ⋮ Unnamed Item

This page was built for publication: