Optimal padded decomposition for bounded treewidth graphs
From MaRDI portal
Cites work
- A constructive proof of the general Lovász local lemma
- A polylogarithmic approximation of the minimum bisection
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- An approximate generalization of the Okamura-Seymour theorem
- Approximate classification via earthmover metrics
- Approximate max-flow min-multicut theorem for graphs of bounded treewidth
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Approximation Algorithms for the 0-Extension Problem
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Clan embeddings into trees, and low treewidth graphs
- Coarse differentiation and multi-flows in planar graphs
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Covering planar metrics (and beyond): O(1) trees suffice
- Cuts, trees and \(\ell_1\)-embeddings of graphs
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Econometrics. An introduction.
- Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
- Excluded minors, network decomposition, and multicommodity flow
- Extending Lipschitz functions via random metric partitions
- Flow-Cut Gaps and Face Covers in Planar Graphs
- scientific article; zbMATH DE number 2079348 (Why is no real title available?)
- scientific article; zbMATH DE number 7595810 (Why is no real title available?)
- scientific article; zbMATH DE number 7650073 (Why is no real title available?)
- Improved lower and upper bounds for universal TSP in planar metrics
- Improved lower bounds for the universal and a priori TSP
- Labeled nearest neighbor search and metric spanners via locality sensitive orderings
- Low treewidth embeddings of planar and minor-free metrics
- Metric decompositions of path-separable graphs
- Metric Embedding via Shortest Path Decompositions
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Minimum 0-extensions of graph metrics
- Multicommodity flows in planar graphs
- Oblivious network design
- On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs
- On Lipschitz embedding of finite metric spaces in Hilbert space
- On tree-partitions of graphs
- On vertex sparsifiers with Steiner nodes
- One tree to rule them all: poly-logarithmic universal Steiner tree
- Optimal lower bounds for universal and differentially private Steiner trees and TSPs
- Relaxed Voronoi: a simple framework for terminal-clustering problems
- Scattering and sparse partitions, and their applications
- Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more
- Spacefilling curves and the planar travelling salesman problem
- Sparse covers for planar graphs and graphs that exclude a fixed minor
- Split and join: strong partitions and universal Steiner trees for graphs
- Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
- Steiner points in tree metrics don't (really) help
- Steiner tree problems
- Strong-diameter decompositions of minor free graphs
- The geometry of graphs and some of its algorithmic applications
- Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
- Universal approximations for TSP, Steiner tree, and set cover
- Vertex sparsifiers and abstract rounding algorithms
- Vertex sparsifiers: new results from old techniques
- Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
This page was built for publication: Optimal padded decomposition for bounded treewidth graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6912579)
