Flows with Unit Path Capacities and Related Packing and Covering Problems

DOI10.1007/978-3-540-85097-7_17MaRDI QIDQ5505656zbMATHOpenAlexFDO

Authors Maren Martens, Martin Skutella

Publication date 27 January 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://depositonce.tu-berlin.de/handle/11303/15639

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Flows with unit path capacities and related packing and covering problems
• Path cover and path pack inequalities for the capacitated fixed-charge network flow problem
• Path packing and a related optimization problem
• Capacitated Confluent Flows: Complexity and Algorithms
• scientific article; zbMATH DE number 3950169
• Packing and covering with integral feasible flows in integral supply-demand networks
• scientific article; zbMATH DE number 3982882
• Integer multiflows and metric packings beyond the cut condition
• Universally maximum flow with piecewise-constant capacities
• scientific article; zbMATH DE number 1342127

Cites work

• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Approximation algorithms for disjoint paths and related routing and packing problems
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Flows on few paths: Algorithms and lower bounds
• Handbook of Approximation Algorithms and Metaheuristics
• Maximal Flow Through a Network
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• The Complexity of Enumeration and Reliability Problems

Cited in

(2)

• Flows with unit path capacities and related packing and covering problems
• scientific article; zbMATH DE number 840702 (Why is no real title available?)

This page was built for publication: Flows with Unit Path Capacities and Related Packing and Covering Problems

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