Strong-diameter decompositions of minor free graphs

DOI10.1007/S00224-010-9283-6zbMath1215.68166OpenAlexW2714858040MaRDI QIDQ613118

Dahlia Malkhi, Udi Wieder, Cyril Gavoille, Ittai Abraham

Publication date: 17 December 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9283-6

zbMATH Keywords

compact routingminor-free graphsstrong-diameter decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (8)

Coloring and Covering Nowhere Dense Graphs ⋮ Reliable Spanners for Metric Spaces ⋮ Unnamed Item ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points

Cites Work

• The extremal function for complete minors
• Approximate distance oracles
• Lower-stretch spanning trees
• Routing with Polynomial Communication-Space Trade-Off
• Compact name-independent routing with minimum stretch
• Object location using path separators
• Excluded minors, network decomposition, and multicommodity flow
• Distributed Computing
• Improved sparse covers for graphs excluding a fixed minor
• Compact oracles for reachability and approximate distances in planar digraphs
• Routing with Improved Communication-Space Trade-Off
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Strong-diameter decompositions of minor free graphs