Approximating disjoint-path problems using greedy algorithms and packing integer programs

DOI10.1007/3-540-69346-7_12MaRDI QIDQ3840354zbMATH OpenFDO

Authors Stavros G. Kolliopoulos, Clifford Stein

Publication date 19 April 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-69346-7_12

zbMATH Keywords

edge and vertex-disjoint path problemspacking integer programspolynomial-time approximationunsplittable flow generalization

Mathematics Subject Classification ID

Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• Approximating disjoint-path problems using packing integer programs
• Approximation algorithms for disjoint paths and related routing and packing problems
• scientific article; zbMATH DE number 5899246
• On the disjoint paths problem

Cited in

(19)

• A note on the greedy algorithm for the unsplittable flow problem
• Approximating covering integer programs with multiplicity constraints
• Approximating disjoint-path problems using packing integer programs
• Approximating low-congestion routing and column-restricted packing problems
• Conversion of coloring algorithms into maximum weight independent set algorithms
• Simple on-line algorithms for the maximum disjoint paths problem
• Finding multiple induced disjoint paths in general graphs
• On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
• Infinite product exponents for modular forms
• Approximation algorithms for disjoint paths and related routing and packing problems
• Shortest node-disjoint paths on random graphs
• A Simple Greedy Algorithm for the k-Disjoint Flow Problem
• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Solving the edge‐disjoint paths problem using a two‐stage method
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• A note on multiflows and treewidth
• Finding disjoint paths with related path costs
• Disjoint paths in sparse graphs

This page was built for publication: Approximating disjoint-path problems using greedy algorithms and packing integer programs

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