Node-searching problem on block graphs

DOI10.1016/j.dam.2007.08.007zbMath1131.68043MaRDI QIDQ2462351

Chin-Wen Ho, Gen-Huey Chen, Hsin-Hung Chou, Ming-Tat Ko

Publication date: 30 November 2007

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

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

zbMATH Keywords

block graphs; path-width; vertex separation; avenue; node-searching problem

Mathematics Subject Classification ID

68P10: Searching and sorting

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

Related Items

Edge Search Number of Cographs in Linear Time, Pathwidth is NP-Hard for Weighted Trees, Edge search number of cographs, On computing a minimum secure dominating set in block graphs, Approximate search strategies for weighted trees, Mixed Search Number of Permutation Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Interval graphs and searching
• Min Cut is NP-complete for edge weighted trees
• Narrowness, pathwidth, and their application in natural language processing
• The vertex separation number of a graph equals its path-width
• On metric properties of certain clique graphs
• Localizing combinatorial properties for partitions on block graphs
• On the pathwidth of chordal graphs
• The vertex separation and search number of a graph
• Treewidth. Computations and approximations
• Graph searching on some subclasses of chordal graphs
• Searching and pebbling
• Optimal path cover problem on block graphs
• Complexity of Finding Embeddings in a k-Tree
• The complexity of searching a graph
• A Characterization of Block-Graphs
• Monotonicity in graph searching
• The Pathwidth and Treewidth of Cographs
• Treewidth and Pathwidth of Permutation Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Characterization of Certain Ptolemaic Graphs