Non-deterministic graph searching in trees

DOI10.1016/J.TCS.2015.02.038MaRDI QIDQ2344776zbMATH OpenOpenAlexFDO

Authors Omid Amini, David Coudert, Nicolas Nisse

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

graph searchingpathwidthtreestreewidth

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2005
• Nondeterministic graph searching: from pathwidth to treewidth
• Monotonicity of Non-deterministic Graph Searching
• Monotonicity of non-deterministic graph searching
• The complexity of searching a graph

Cites work

• A distributed algorithm for computing the node search number in trees
• An annotated bibliography on guaranteed graph searching
• Approximation of pathwidth of outerplanar graphs
• Computing the vertex separation of unicyclic graphs
• Connected 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
• Graph minors. II. Algorithmic aspects of tree-width
• Graph searching and a min-max theorem for tree-width
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• Monotonicity in graph searching
• Monotonicity of non-deterministic graph searching
• Nondeterministic graph searching: from pathwidth to treewidth
• On the pathwidth of chordal graphs
• Pathwidth of outerplanar graphs
• The complexity of searching a graph
• The vertex separation and search number of a graph

Cited in

(6)

• Nondeterministic graph searching: from pathwidth to treewidth
• Parameterized algorithms for non-separating trees and branchings in digraphs
• Monotonicity of Non-deterministic Graph Searching
• Unbounded search and recursive graph problems
• Mathematical Foundations of Computer Science 2005
• Monotonicity of non-deterministic graph searching

This page was built for publication: Non-deterministic graph searching in trees

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