Metric decompositions of path-separable graphs

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

zbMATH Keywords

randomized algorithmspadded metric decompositionpath-separable graphs

Mathematics Subject Classification ID

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)

Metric Embedding via Shortest Path Decompositions ⋮ Unnamed Item

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