Strong-diameter decompositions of minor free graphs
DOI10.1007/S00224-010-9283-6zbMATH Open1215.68166OpenAlexW2714858040MaRDI QIDQ613118FDOQ613118
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
Recommendations
- Strong complete minors in digraphs
- Decompositions into subgraphs of small diameter
- A decomposition for strongly perfect graphs
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Strongly regular decompositions of the complete graph
- Structural and spectral properties of minimal strong digraphs
- On the strong partition dimension of graphs
- Simplicial minors and decompositions of graphs
- Minimal strong connected digraphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- The extremal function for complete minors
- Approximate distance oracles
- Compact oracles for reachability and approximate distances in planar digraphs
- Excluded minors, network decomposition, and multicommodity flow
- Object location using path separators
- Lower-stretch spanning trees
- Compact name-independent routing with minimum stretch
- Distributed Computing
- Routing with Polynomial Communication-Space Trade-Off
- Improved sparse covers for graphs excluding a fixed minor
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Routing with Improved Communication-Space Trade-Off
Cited In (8)
- Title not available (Why is that?)
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Coloring and Covering Nowhere Dense Graphs
- Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
- Reliable Spanners for Metric Spaces
- Colouring and Covering Nowhere Dense Graphs
- Sparse covers for planar graphs and graphs that exclude a fixed minor
- Space-efficient path-reporting approximate distance oracles
This page was built for publication: Strong-diameter decompositions of minor free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q613118)
