Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871115 | Discrete Applied Mathematics | 2018 | 8 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
H.B. de Macedo Filho, C.M.H. de Figueiredo, Z. Li, R.C.S. Machado,