scientific article; zbMATH DE number 7413501
From MaRDI portal
Publication:5158500
DOI10.4086/toc.2021.v017a006OpenAlexW3200593310MaRDI QIDQ5158500
David H. Kim, Julia Chuzhoy, Rachit Nimavat
Publication date: 25 October 2021
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2021.v017a006
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Theory of computing (68Qxx)
Related Items (1)
Cites Work
- Unnamed Item
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Randomized rounding: A technique for provably good algorithms and algorithmic proofs
- Approximations for the disjoint paths problem in high-diameter planar networks
- Approximating disjoint-path problems using packing integer programs
- New algorithms for maximum disjoint paths based on tree-likeness
- Graph minors. XIII: The disjoint paths problem
- Maximum edge-disjoint paths in planar graphs with congestion 2
- Edge-Disjoint Paths in Expander Graphs
- Routing in Undirected Graphs with Constant Congestion
- Detecting high log-densities
- Graph expansion and the unique games conjecture
- An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- Parallel Repetition in Projection Games and a Concentration Bound
- Logarithmic hardness of the undirected edge-disjoint paths problem
- Multicommodity demand flow in a tree and packing integer programs
- Multicommodity flow, well-linked terminals, and routing problems
- A Separator Theorem for Planar Graphs
- On the Computational Complexity of Combinatorial Problems
- On the Complexity of Timetable and Multicommodity Flow Problems
- Optimal Construction of Edge-Disjoint Paths in Random Graphs
- Planar Separators
- Existence and Construction of Edge-Disjoint Paths on Expander Graphs
- A Parallel Repetition Theorem
- Approximating theDomatic Number
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- Almost polynomial hardness of node-disjoint paths in grids
- Improved approximation for node-disjoint paths in planar graphs
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- A Theorem on Planar Graphs
- Edge Disjoint Paths in Moderately Connected Graphs
This page was built for publication:
