Article ID Journal Published Year Pages File Type
420838 Discrete Applied Mathematics 2008 21 Pages PDF
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
, , , ,