Name
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2007.08.007 | Discrete Applied Mathematics |
Keywords | Field | DocType |
avenue concept,node-searching problem,important problem,search number,path-width problem,optimal search strategy,interval thickness problem,block graph,vertex separation problem,efficient algorithm,polynomial time | Discrete mathematics,Combinatorics,Indifference graph,Tree (graph theory),Chordal graph,Block design,Constraint satisfaction dual problem,Vertex cover,Time complexity,Longest path problem,Mathematics | Journal |
Volume | Issue | ISSN |
156 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
7 | 0.45 | 21 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hsin-Hung Chou | 1 | 54 | 5.37 |
| Ming-Tat Ko | 2 | 1320 | 103.71 |
| Chin-Wen Ho | 3 | 573 | 39.27 |
| Gen-Huey Chen | 4 | 979 | 89.32 |