Connected graph searching in chordal graphs

DOI10.1016/j.dam.2008.08.007zbMath1211.05037MaRDI QIDQ967304

Nicolas Nisse

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.007

zbMATH Keywords

treewidth; chordal graphs; graph searching

Mathematics Subject Classification ID

68P10: Searching and sorting

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

Related Items

Pathwidth is NP-Hard for Weighted Trees, Connected graph searching, Connected searching of weighted trees, An annotated bibliography on guaranteed graph searching, Approximate search strategies for weighted trees, Distributed graph searching with a sense of direction

Cites Work

• On the pathwidth of chordal graphs
• Graph searching and a min-max theorem for tree-width
• Treewidth for graphs with small chordality
• Characterizations and algorithmic applications of chordal graph embeddings
• Fugitive-search games on graphs and related parameters
• Searching and pebbling
• Connected Treewidth and Connected Graph Searching
• Graph minors. II. Algorithmic aspects of tree-width
• The complexity of searching a graph
• Monotonicity in graph searching
• Treewidth of Chordal Bipartite Graphs
• Recontamination does not help to search a graph
• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item