Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs

DOI10.1137/17M1112406zbMath1432.05077arXiv1311.3048OpenAlexW2953101896WikidataQ127828154 ScholiaQ127828154MaRDI QIDQ5232322

Ittai Abraham, Ofer Neiman, Kunal Talwar, Cyril Gavoille, Anupam Gupta

Publication date: 2 September 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

excluded minorcops and robberpadded decomposition

Mathematics Subject Classification ID

Games involving graphs (91A43) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (6)

Metric Embedding via Shortest Path Decompositions ⋮ Reliable Spanners for Metric Spaces ⋮ Cops and robber on oriented graphs with respect to push operation ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ Light spanners for high dimensional norms via stochastic decompositions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong-diameter decompositions of minor free graphs
• Randomly removing \(g\) handles at once
• On a pursuit game played on graphs for which a minor is excluded
• Low diameter graph decompositions
• Graph minors. XVI: Excluding a non-planar graph
• Extending Lipschitz functions via random metric partitions
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• On average distortion of embedding metrics into the line and into L ₁
• Shortest Cut Graph of a Surface with Prescribed Vertex Set
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Complexity of network synchronization
• A Separator Theorem for Nonplanar Graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Approximation Algorithms for the 0-Extension Problem
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Higher Eigenvalues of Graphs
• Excluded minors, network decomposition, and multicommodity flow
• Cops, robbers, and threatening skeletons
• Improved sparse covers for graphs excluding a fixed minor
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
• Sparsest cut on bounded treewidth graphs
• 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: Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs