|
|||||
|
|
Node-searching problem on block graphs |
|
| Authors: | Hsin-Hung Chou Ming-Tat Ko |
| Institution: | a Department of Information Management, Chang Jung Christian University, 396 Chang Jung Road, Section 1, Kway Jen, Tainan 711, Taiwan b Institute of Information Science, Academia Sinica, Taiwan c Department of Computer Science and Information Engineering, National Central University, Taiwan d Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan |
| 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. |
| Keywords: | Avenue Block graphs Node-searching problem Path-width Vertex separation |
| 本文献已被 ScienceDirect 等数据库收录！ | |