Node-searching problem on block graphs
Resource
Discrete Applied Mathematics 156 (1): 55-75
Journal
Discrete Applied Mathematics
Pages
55-75
Date Issued
2008
Date
2008
Author(s)
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. © 2007 Elsevier B.V. All rights reserved.
Subjects
Avenue; Block graphs; Node-searching problem; Path-width; Vertex separation
Other Subjects
Algorithms; Optimal control systems; Polynomial approximation; Problem solving; Block graphs; Node-searching problems; Path-width; Vertex separation; Graph theory
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
47.pdf
Size
368.2 KB
Format
Adobe PDF
Checksum
(MD5):4e7a6f4778d2909fa77ebb6bb4a4d67a