Nondeterministic graph searching: from pathwidth to treewidth

DOI10.1007/s00453-007-9041-6zbMath1172.68046OpenAlexW2011280829WikidataQ60488693 ScholiaQ60488693MaRDI QIDQ1024783

Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse

Publication date: 17 June 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9041-6

zbMATH Keywords

treewidthpathwidthgraph searching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Constructing Brambles ⋮ Jumping robbers in digraphs ⋮ Characterizing width two for variants of treewidth ⋮ Edge Search Number of Cographs in Linear Time ⋮ Connected search for a lazy robber ⋮ A distributed algorithm for computing the node search number in trees ⋮ Cooperative exploration and protection of a workspace assisted by information networks ⋮ Connected graph searching ⋮ Non-deterministic graph searching in trees

Cites Work

• Unnamed Item
• Unnamed Item
• On minimizing width in linear layouts
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Call routing and the ratcatcher
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• Searching and pebbling
• A Dynamic Programming Approach to Sequencing Problems
• Pathwidth of outerplanar graphs
• On self duality of pathwidth in polyhedral graph embeddings
• Monotonicity of Non-deterministic Graph Searching
• Improved approximation algorithms for minimum-weight vertex separators
• Topological Bandwidth
• Complexity of Finding Embeddings in a k-Tree
• Finding a Maximum Independent Set
• Automata, Languages and Programming