scientific article; zbMATH DE number 7650073

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.6MaRDI QIDQ5875457

Arnold Filtser

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1906.09783

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

spannersdoubling dimensiondistance oraclesunique gamesstrong diameterminor free graphspadded decompositionsparse cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (2)

Unnamed Item ⋮ Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Space-efficient path-reporting approximate distance oracles
• Strong-diameter decompositions of minor free graphs
• Low diameter graph decompositions
• Graph minors. XVI: Excluding a non-planar graph
• Metric decompositions of path-separable graphs
• Sparse covers for planar graphs and graphs that exclude a fixed minor
• A constructive proof of the general lovász local lemma
• On the power of unique 2-prover 1-round games
• On average distortion of embedding metrics into the line and into L ₁
• Lower-Stretch Spanning Trees
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
• Complexity of network synchronization
• Ramsey Spanning Trees and Their Applications
• Using Petal-Decompositions to Build a Low Stretch Spanning Tree
• Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
• Approximation Algorithms for the 0-Extension Problem
• A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs
• Approximating Unique Games Using Low Diameter Graph Decomposition
• Greedy spanners are optimal in doubling metrics
• Excluded minors, network decomposition, and multicommodity flow
• Cops, robbers, and threatening skeletons
• The Greedy Spanner is Existentially Optimal
• Vertex Sparsifiers: New Results from Old Techniques
• The NP-completeness column: An ongoing guide
• Advances in metric embedding theory
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: