Sparse covers for planar graphs and graphs that exclude a fixed minor

DOI10.1007/S00453-013-9757-4MaRDI QIDQ2249746zbMATH OpenOpenAlexWikidataFDO

Authors Costas Busch, Ryan Lafortune, Srikanta Tirthapura

Publication date 3 July 2014

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://lib.dr.iastate.edu/ece_pubs/180

zbMATH Keywords

shortest path clustering

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph minors (05C83)

Recommendations

• Improved sparse covers for graphs excluding a fixed minor
• Strong-diameter decompositions of minor free graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• A local algorithm for constructing spanners in minor-free graphs
• Distributed Computing

Cites work

• A trade-off between space and efficiency for routing tables
• Approximation algorithms for NP-complete problems on planar graphs
• Compact and localized distributed data structures
• Compact name-independent routing with minimum stretch
• Compact oracles for reachability and approximate distances in planar digraphs
• Compact Routing with Name Independence
• Complexity of network synchronization
• Distance-dependent distributed directories
• Distributed Computing
• Distributed Computing: A Locality-Sensitive Approach
• Efficient Message Routing in Planar Networks
• Excluded minors, network decomposition, and multicommodity flow
• Graph minors. V. Excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• Improved lower and upper bounds for universal TSP in planar metrics
• Object location using path separators
• Oblivious buy-at-bulk in planar graphs
• Oblivious network design
• Online tracking of mobile users
• Optimal scale-free compact routing schemes in networks of low doubling dimension
• Optimal-stretch name-independent compact routing in doubling metrics
• Strong-diameter decompositions of minor free graphs
• Universal approximations for TSP, Steiner tree, and set cover

Cited in

(12)

• Sparse obstructions for minor-covering parameters
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Improved sparse covers for graphs excluding a fixed minor
• scientific article; zbMATH DE number 7650073 (Why is no real title available?)
• Compact Routing in Unit Disk Graphs
• Reliable Spanners for Metric Spaces
• Scattering and sparse partitions, and their applications
• Optimal padded decomposition for bounded treewidth graphs
• Scattering and sparse partitions, and their applications
• Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
• On sparse covers of minor free graphs, low dimensional metric embeddings, and other applications
• Going beyond surfaces in diameter approximation

This page was built for publication: Sparse covers for planar graphs and graphs that exclude a fixed minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249746)