Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems
From MaRDI portal
Publication:5136261
DOI10.4230/LIPIcs.ISAAC.2017.41zbMath1457.68308arXiv1709.10307OpenAlexW2963439954MaRDI QIDQ5136261
Hadi Khodabande, Bo Qin, Mordecai J. Golin
Publication date: 25 November 2020
Full work available at URL: https://arxiv.org/abs/1709.10307
Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Flows in graphs (05C21)
Related Items (1)
Cites Work
- Unnamed Item
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- The directed subgraph homeomorphism problem
- Graph minors. XIII: The disjoint paths problem
- Multicommodity flows over time: Efficient algorithms and complexity
- A comprehensive survey on the quickest path problem
- Polynomial-time algorithms for special cases of the maximum confluent flow problem
- The Quickest Transshipment Problem
- An Introduction to Network Flows over Time
- (Almost) Tight bounds and existence theorems for single-commodity confluent flows
- Meet and merge
- Maximum Flows on Disjoint Paths
- Traffic Networks and Flows over Time
- Constructing Maximal Dynamic Flows from Static Flows
- Routing and Capacity Optimization for IP Networks
- A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
- Constraint satisfaction, packet routing, and the lovasz local lemma
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
This page was built for publication: Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems
