Nondeterministic graph searching: from pathwidth to treewidth
From MaRDI portal
Publication:1024783
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
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
