Metric decompositions of path-separable graphs
type: Item
instance of: scholarly article
title: Metric decompositions of path-separable graphs
zbMATH Open document ID: 1380.68437
author: Lior Kamma
author: Robert Krauthgamer
published in: Algorithmica
publication date: 2017-11-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/1504.07019
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6804030
zbMATH Keywords: path-separable graphs
zbMATH Keywords: padded metric decomposition
zbMATH Keywords: randomized algorithms
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2259676875
arXiv ID: 1504.07019
cites work: Object location using path separators
cites work: Cops, robbers, and threatening skeletons
cites work: Plongements lipschitziens dans ${\bbfR}\sp n$
cites work: Vertex sparsifiers: new results from old techniques
cites work: On hierarchical routing in doubling metrics
cites work: Approximation Algorithms for the 0-Extension Problem
cites work: Path Separability of Graphs
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Cutting Corners Cheaply, or How to Remove Steiner Points
cites work: Ramsey partitions and proximity data structures
cites work: Measured descent: A new embedding method for finite metrics
cites work: Excluded minors, network decomposition, and multicommodity flow
cites work: Q5417618
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: Bypassing the embedding
cites work: Compact oracles for reachability and approximate distances in planar digraphs
DOI: 10.1007/S00453-016-0213-0
Recommended article: Path Separability of Graphs
Recommended article: Path decompositions of multigraphs
Recommended article: Path decomposition of graphs with given path length
Recommended article: On the path separation number of graphs
Recommended article: Q4234145
Recommended article: Q5087460
Recommended article: On the decomposition of the Laplacian on metric graphs
Recommended article: Q5212369
Recommended article: The decomposition dimension of graphs
description: scientific article