کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871115 | 1440178 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Using SPQR-trees to speed up recognition algorithms based on 2-cutsets Using SPQR-trees to speed up recognition algorithms based on 2-cutsets](/preview/png/6871115.png)
چکیده انگلیسی
Several well-studied classes of graphs admit structural characterizations via proper 2-cutsets which lead to polynomial-time recognition algorithms. The algorithms so far obtained for those recognition problems do not guarantee linear-time complexity. The bottleneck to those algorithms is the Ω(nm)-time complexity to fully decompose by proper 2-cutsets a graph with n vertices and m edges. In the present work, we investigate the 3-connected components of a graph and propose the use of the SPQR-tree data structure to obtain a fully decomposed graph in linear time. As a consequence, we show that the recognition of chordless graphs and of graphs that do not contain a propeller as a subgraph can be done in linear time, answering questions in the existing literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 101-108
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 101-108
نویسندگان
H.B. de Macedo Filho, C.M.H. de Figueiredo, Z. Li, R.C.S. Machado,