Approximate search strategies for weighted trees
From MaRDI portal
Publication:1929222
DOI10.1016/j.tcs.2012.07.006zbMath1253.05131MaRDI QIDQ1929222
Publication date: 7 January 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.006
05C05: Trees
91A43: Games involving graphs
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
05C22: Signed and weighted graphs
Related Items
On-line search in two-dimensional environment, Searching by heterogeneous agents, Network decontamination under \(m\)-immunity, Distributed graph searching with a sense of direction
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing the vertex separation of unicyclic graphs
- Connected graph searching
- Connected searching of weighted trees
- An annotated bibliography on guaranteed graph searching
- Connected graph searching in chordal graphs
- Sweeping graphs with large clique number
- Interval graphs and searching
- Graph minors. X: Obstructions to tree-decomposition
- The vertex separation number of a graph equals its path-width
- A partial k-arboretum of graphs with bounded treewidth
- On the pathwidth of chordal graphs
- The vertex separation and search number of a graph
- Searching and pebbling
- Node-searching problem on block graphs
- Approximation of pathwidth of outerplanar graphs
- Pathwidth of Circular-Arc Graphs
- Improved approximation algorithms for minimum-weight vertex separators
- The complexity of searching a graph
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Treewidth and Pathwidth of Permutation Graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Recontamination does not help to search a graph
- Pathwidth is NP-Hard for Weighted Trees
- A 3-approximation for the pathwidth of Halin graphs
- Graph-Theoretic Concepts in Computer Science
