Non-deterministic graph searching in trees

DOI10.1016/j.tcs.2015.02.038zbMath1314.68148OpenAlexW2086958144MaRDI QIDQ2344776

David Coudert, Nicolas Nisse, Omid Amini

Publication date: 18 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.038

zbMATH Keywords

treewidthtreespathwidthgraph searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57)

Related Items

Searching by heterogeneous agents

Cites Work

• Unnamed Item
• Computing the vertex separation of unicyclic graphs
• Connected graph searching
• Monotonicity of non-deterministic graph searching
• An annotated bibliography on guaranteed graph searching
• Nondeterministic graph searching: from pathwidth to treewidth
• On the pathwidth of chordal graphs
• Graph searching and a min-max theorem for tree-width
• The vertex separation and search number of a graph
• A distributed algorithm for computing the node search number in trees
• Approximation of pathwidth of outerplanar graphs
• Pathwidth of outerplanar graphs
• Graph minors. II. Algorithmic aspects of tree-width
• The complexity of searching a graph
• Monotonicity in graph searching
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs