Flows with unit path capacities and related packing and covering problems
type: Item
instance of: scholarly article
title: Flows with unit path capacities and related packing and covering problems
zbMATH Open document ID: 1176.90072
author: Maren Martens
author: Martin Skutella
published in: Journal of Combinatorial Optimization
publication date: 2009-12-02T00:00:00Z
full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15639
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 5641549
zbMATH Keywords: network flows
zbMATH Keywords: approximation algorithms
zbMATH Keywords: packing problems
zbMATH Keywords: covering problems
MaRDI profile type: Publication
OpenAlex ID: W2797242861
cites work: Hardness of the Undirected Congestion Minimization Problem
cites work: Length-Bounded Cuts and Flows
cites work: Counting paths in graphs
cites work: Approximation algorithms for disjoint paths and related routing and packing problems
cites work: Q4471352
cites work: A note on two problems in connexion with graphs
cites work: An Appraisal of Some Shortest-Path Algorithms
cites work: Finding the k Shortest Paths
cites work: Approximating fractional multicommodity flow independent of the number of commodities
cites work: Maximal Flow Through a Network
cites work: Counting paths in Young's lattice
cites work: An exponential‐function reduction method for block‐angular convex programs
cites work: A sublinear-time randomized approximation algorithm for matrix games
cites work: Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
cites work: Coordination Complexity of Parallel Price-Directive Decomposition
cites work: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
cites work: Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
cites work: Approximating disjoint-path problems using packing integer programs
cites work: A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
cites work: Fast approximation algorithms for multicommodity flow problems
cites work: Q3584085
cites work: Flows on few paths: Algorithms and lower bounds
cites work: Q4298260
cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: Q2934682
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: The maximum concurrent flow problem
cites work: A matrix for counting paths in acyclic digraphs
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Finding the K Shortest Loopless Paths in a Network
DOI: 10.1007/S10878-009-9225-X
description: scientific article; zbMATH DE number 5641549