Node-searching problem on block graphs

DOI10.1016/j.dam.2007.08.007zbMath1131.68043OpenAlexW2079812956MaRDI 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 graphspath-widthvertex separationavenuenode-searching problem

Mathematics Subject Classification ID

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

Related Items (6)

Edge Search Number of Cographs in Linear Time ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Approximate search strategies for weighted trees ⋮ Mixed Search Number of Permutation Graphs ⋮ Edge search number of cographs ⋮ On computing a minimum secure dominating set in block 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

This page was built for publication: Node-searching problem on block graphs