کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434158 689692 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Characterizing and recognizing probe block graphs
ترجمه فارسی عنوان
تشخیص و شناسایی نمودار بلوک پروب؟
کلمات کلیدی
اصلاح نمودار، نمودار پروب، بلوک نمودار، پروب بلوک گراف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Block graphs are graphs in which every block (biconnected component) is a clique. A graph G=(V,E)G=(V,E) is said to be an (unpartitioned) probe block graph if there exist an independent set N⊆VN⊆V and some set E′⊆(N2) such that the graph G′=(V,E∪E′)G′=(V,E∪E′) is a block graph; if such an independent set N is given, G is called a partitioned probe block graph. In this note we give good characterizations for probe block graphs, in both unpartitioned and partitioned cases. As a result, partitioned and unpartitioned probe block graphs can be recognized in linear time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 568, 23 February 2015, Pages 97–102
نویسندگان
, ,