Approximating disjoint-path problems using packing integer programs

zbMath1059.90107MaRDI QIDQ1424288

Stavros G. Kolliopoulos, Clifford Stein

Publication date: 11 March 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmedge-disjoint pathpacking integer program

Mathematics Subject Classification ID

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

Related Items (18)

Hardness and approximation results for packing Steiner trees ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Unnamed Item ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ Iterative Packing for Demand and Hypergraph Matching ⋮ Balanced paths in acyclic networks: Tractable cases and related approaches ⋮ Routing with congestion in acyclic digraphs ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Solving the maximum edge disjoint path problem using a modified Lagrangian particle swarm optimisation hybrid ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Unnamed Item ⋮ Flows with unit path capacities and related packing and covering problems ⋮ Minimum-cost single-source 2-splittable flow ⋮ Unnamed Item

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