Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420838 | Discrete Applied Mathematics | 2008 | 21 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hsin-Hung Chou, Ming-Tat Ko, Chin-Wen Ho, Gen-Huey Chen,