Nondeterministic graph searching: from pathwidth to treewidth
From MaRDI portal
Publication:1024783
DOI10.1007/S00453-007-9041-6zbMATH Open1172.68046OpenAlexW2011280829WikidataQ60488693 ScholiaQ60488693MaRDI QIDQ1024783FDOQ1024783
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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph minors. X: Obstructions to tree-decomposition
- Graph searching and a min-max theorem for tree-width
- A Dynamic Programming Approach to Sequencing Problems
- A partial k-arboretum of graphs with bounded treewidth
- Call routing and the ratcatcher
- Searching and pebbling
- Complexity of Finding Embeddings in a k-Tree
- The vertex separation and search number of a graph
- Fugitive-search games on graphs and related parameters
- Topological Bandwidth
- On minimizing width in linear layouts
- Finding a Maximum Independent Set
- On self duality of pathwidth in polyhedral graph embeddings
- Improved approximation algorithms for minimum-weight vertex separators
- Automata, Languages and Programming
- Monotonicity of Non-deterministic Graph Searching
- Pathwidth of outerplanar graphs
Cited In (10)
- Non-deterministic graph searching in trees
- Edge Search Number of Cographs in Linear Time
- Graph searching and a min-max theorem for tree-width
- Cooperative exploration and protection of a workspace assisted by information networks
- Connected graph searching
- Jumping robbers in digraphs
- Characterizing width two for variants of treewidth
- Constructing Brambles
- Connected search for a lazy robber
- A distributed algorithm for computing the node search number 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)
