Cutting Corners Cheaply, or How to Remove Steiner Points
From MaRDI portal
Publication:5502176
DOI10.1137/140951382zbMath1328.05059arXiv1304.1449OpenAlexW2569472613MaRDI QIDQ5502176
No author found.
Publication date: 18 August 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.1449
Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Discrete geometry (52C99) Randomized algorithms (68W20)
Related Items (8)
Terminal embeddings ⋮ Metric decompositions of path-separable graphs ⋮ Vertex Sparsification in Trees ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Distance-Preserving Subgraphs of Interval Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Strong-diameter decompositions of minor free graphs
- An improved approximation algorithm for requirement cut
- Ramsey partitions and proximity data structures
- Low diameter graph decompositions
- Extending Lipschitz functions via random metric partitions
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Preserving Terminal Distances Using Minors
- Extensions and limits to vertex sparsification
- Approximate distance oracles
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Graph spanners
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Twice-ramanujan sparsifiers
- Excluded minors, network decomposition, and multicommodity flow
- On vertex sparsifiers with Steiner nodes
- Algorithms – ESA 2004
- Vertex Sparsifiers: New Results from Old Techniques
- A tight bound on approximating arbitrary metrics by tree metrics
This page was built for publication: Cutting Corners Cheaply, or How to Remove Steiner Points
