Contraction obstructions for connected graph searching

DOI10.1016/j.dam.2015.07.036zbMath1339.05210arXiv1410.8756OpenAlexW1717727751MaRDI QIDQ298950

Dimitris Zoros, Dimitrios M. Thilikos, Arvind Kumar Gupta, Micah J. Best

Publication date: 21 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph contractionsgraph searchingobstruction set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (5)

Sparse obstructions for minor-covering parameters ⋮ Connected search for a lazy robber ⋮ A connected version of the graph coloring game ⋮ On-line search in two-dimensional environment ⋮ Finding small-width connected path decompositions in polynomial time

Cites Work

• Connected graph searching
• Graph minors. XX: Wagner's conjecture
• An annotated bibliography on guaranteed graph searching
• Graph minors. I. Excluding a forest
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Graph searching and a min-max theorem for tree-width
• Obstruction set isolation for the gate matrix layout problem
• Fugitive-search games on graphs and related parameters
• On the monotonicity of games generated by symmetric submodular functions.
• Algorithms and obstructions for linear-width and related search parameters
• Graph minors. XIII: The disjoint paths problem
• Monotony Properties of Connected Visible Graph Searching
• Graph minors. II. Algorithmic aspects of tree-width
• Monotonicity in graph searching
• From Pathwidth to Connected Pathwidth
• Recontamination does not help to search a graph
• Parameterized and Exact Computation
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Contraction obstructions for connected graph searching