Metric decompositions of path-separable graphs
From MaRDI portal
Publication:1679219
DOI10.1007/s00453-016-0213-0zbMath1380.68437arXiv1504.07019OpenAlexW2259676875MaRDI QIDQ1679219
Robert Krauthgamer, Lior Kamma
Publication date: 9 November 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.07019
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Ramsey partitions and proximity data structures
- Measured descent: A new embedding method for finite metrics
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Bypassing the embedding
- Path Separability of Graphs
- Plongements lipschitziens dans ${\bbfR}\sp n$
- Approximation Algorithms for the 0-Extension Problem
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Object location using path separators
- Excluded minors, network decomposition, and multicommodity flow
- Cops, robbers, and threatening skeletons
- Compact oracles for reachability and approximate distances in planar digraphs
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Vertex Sparsifiers: New Results from Old Techniques
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: Metric decompositions of path-separable graphs