Connected graph searching in chordal graphs

DOI10.1016/j.dam.2008.08.007zbMath1211.05037OpenAlexW1972027829MaRDI 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

treewidthchordal graphsgraph searching

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items (10)

Pathwidth is NP-Hard for Weighted Trees ⋮ Approximate search strategies for weighted trees ⋮ Black Virus Decontamination of Synchronous Ring Networks by Initially Scattered Mobile Agents ⋮ Connected search for a lazy robber ⋮ Network decontamination under \(m\)-immunity ⋮ An annotated bibliography on guaranteed graph searching ⋮ Connected graph searching ⋮ Connected searching of weighted trees ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Distributed graph searching with a sense of direction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Connected graph searching in chordal graphs