کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420838 683991 2008 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Node-searching problem on block graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Node-searching problem on block graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 1, 1 January 2008, Pages 55–75
نویسندگان
, , , ,