Improved sparse covers for graphs excluding a fixed minor

DOI10.1145/1281100.1281112zbMath1283.68080OpenAlexW2119483402WikidataQ60148598 ScholiaQ60148598MaRDI QIDQ5401394

Srikanta Tirthapura, Costas Busch, Ryan Lafortune

Publication date: 13 March 2014

Published in: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1281100.1281112

zbMATH Keywords

planar graphminor free graphcompact routingpath separatorsparse cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14)

Related Items (7)

Strong-diameter decompositions of minor free graphs ⋮ Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Oblivious Buy-at-Bulk in Planar Graphs ⋮ Unnamed Item ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs

This page was built for publication: Improved sparse covers for graphs excluding a fixed minor