Node-searching problem on block graphs

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

研究成果: 雜誌貢獻期刊論文同行評審

6 引文 斯高帕斯(Scopus)

摘要

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.

原文???core.languages.en_GB???
頁(從 - 到)55-75
頁數21
期刊Discrete Applied Mathematics
156
發行號1
DOIs
出版狀態已出版 - 1 1月 2008

指紋

深入研究「Node-searching problem on block graphs」主題。共同形成了獨特的指紋。

引用此