Flows with unit path capacities and related packing and covering problems
From MaRDI portal
Publication:1041430
DOI10.1007/s10878-009-9225-xzbMath1176.90072OpenAlexW2797242861MaRDI QIDQ1041430
Martin Skutella, Maren Martens
Publication date: 2 December 2009
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15639
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Counting paths in Young's lattice
- Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
- Approximating disjoint-path problems using packing integer programs
- Counting paths in graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Fast approximation algorithms for multicommodity flow problems
- A matrix for counting paths in acyclic digraphs
- A sublinear-time randomized approximation algorithm for matrix games
- Approximating Fractional Multicommodity Flow Independent of the Number of Commodities
- Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
- Maximal Flow Through a Network
- The maximum concurrent flow problem
- Length-Bounded Cuts and Flows
- The Complexity of Enumeration and Reliability Problems
- Finding the k Shortest Paths
- Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- An exponential‐function reduction method for block‐angular convex programs
- Coordination Complexity of Parallel Price-Directive Decomposition
- Hardness of the Undirected Congestion Minimization Problem
- Flows on few paths: Algorithms and lower bounds
- An Appraisal of Some Shortest-Path Algorithms
- Finding the K Shortest Loopless Paths in a Network
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems