Nondeterministic graph searching: from pathwidth to treewidth

DOI10.1007/S00453-007-9041-6MaRDI QIDQ1024783zbMATH OpenOpenAlexWikidataFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Mathematical Foundations of Computer Science 2005
• Non-deterministic graph searching in trees
• scientific article; zbMATH DE number 176249
• Monotonicity of non-deterministic graph searching
• scientific article; zbMATH DE number 176762

Cites work

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

Cited in

(11)

• A distributed algorithm for computing the node search number in trees
• Jumping robbers in digraphs
• Characterizing width two for variants of treewidth
• Constructing Brambles
• Cooperative exploration and protection of a workspace assisted by information networks
• Connected search for a lazy robber
• Connected graph searching
• Mathematical Foundations of Computer Science 2005
• Graph searching and a min-max theorem for tree-width
• Edge Search Number of Cographs in Linear Time
• Non-deterministic graph searching in trees

This page was built for publication: Nondeterministic graph searching: from pathwidth to treewidth

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