https://scholars.lib.ntu.edu.tw/handle/123456789/118063
標題: | Node-searching problem on block graphs | 作者: | Chou, Hsin-Hung Ko, Ming-Tat Ho, Chin-Wen Chen, Gen-Huey |
關鍵字: | Avenue; Block graphs; Node-searching problem; Path-width; Vertex separation | 公開日期: | 2008 | 起(迄)頁: | 55-75 | 來源出版物: | Discrete Applied Mathematics | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-35648991356&doi=10.1016%2fj.dam.2007.08.007&partnerID=40&md5=34c23df13b720e008c9b89ebd5a64df4 | DOI: | 10.1016/j.dam.2007.08.007 | SDG/關鍵字: | Algorithms; Optimal control systems; Polynomial approximation; Problem solving; Block graphs; Node-searching problems; Path-width; Vertex separation; Graph theory |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。