Node-searching problem on block graphs

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

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

The node-searching problem, introduced by Kirousis and Papadimitriou, is equivalent to several important problems, such as the interval thickness problem, the path-width problem, the vertex separation problem, and so on. In this paper, we generalize the avenue concept, originally proposed for trees, to block graphs whereby we design an efficient algorithm for computing both the search numbers and optimal search strategies for block graphs. It answers the question proposed by Peng et al. of whether the node-searching problem on block graphs can be solved in polynomial time.

Original languageEnglish
Pages (from-to)55-75
Number of pages21
JournalDiscrete Applied Mathematics
Volume156
Issue number1
DOIs
StatePublished - 1 Jan 2008

Keywords

  • Avenue
  • Block graphs
  • Node-searching problem
  • Path-width
  • Vertex separation

Fingerprint

Dive into the research topics of 'Node-searching problem on block graphs'. Together they form a unique fingerprint.

Cite this