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


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
Issue number1
StatePublished - 1 Jan 2008


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


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

Cite this