Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets

The problem of counting the number of independent sets of a graph G (denoted as i(G)) is a classic #P-complete problem. We present some patterns on graphs that allows us the polynomial computation of i(G). For example, we show that for a graph G where its set of cycles can be arranged as embedded cy...

Descripción completa

Detalles Bibliográficos
Autores principales: De Ita, Guillermo, Rodríguez, Miguel, Bello, Pedro, Contreras, Meliza
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7297590/
http://dx.doi.org/10.1007/978-3-030-49076-8_6
_version_ 1783547038509563904
author De Ita, Guillermo
Rodríguez, Miguel
Bello, Pedro
Contreras, Meliza
author_facet De Ita, Guillermo
Rodríguez, Miguel
Bello, Pedro
Contreras, Meliza
author_sort De Ita, Guillermo
collection PubMed
description The problem of counting the number of independent sets of a graph G (denoted as i(G)) is a classic #P-complete problem. We present some patterns on graphs that allows us the polynomial computation of i(G). For example, we show that for a graph G where its set of cycles can be arranged as embedded cycles, i(G) can be computed in polynomial time. Particularly, our proposal counts independent sets on outerplanar graphs.
format Online
Article
Text
id pubmed-7297590
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72975902020-06-17 Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets De Ita, Guillermo Rodríguez, Miguel Bello, Pedro Contreras, Meliza Pattern Recognition Article The problem of counting the number of independent sets of a graph G (denoted as i(G)) is a classic #P-complete problem. We present some patterns on graphs that allows us the polynomial computation of i(G). For example, we show that for a graph G where its set of cycles can be arranged as embedded cycles, i(G) can be computed in polynomial time. Particularly, our proposal counts independent sets on outerplanar graphs. 2020-04-29 /pmc/articles/PMC7297590/ http://dx.doi.org/10.1007/978-3-030-49076-8_6 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
De Ita, Guillermo
Rodríguez, Miguel
Bello, Pedro
Contreras, Meliza
Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets
title Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets
title_full Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets
title_fullStr Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets
title_full_unstemmed Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets
title_short Basic Pattern Graphs for the Efficient Computation of Its Number of Independent Sets
title_sort basic pattern graphs for the efficient computation of its number of independent sets
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7297590/
http://dx.doi.org/10.1007/978-3-030-49076-8_6
work_keys_str_mv AT deitaguillermo basicpatterngraphsfortheefficientcomputationofitsnumberofindependentsets
AT rodriguezmiguel basicpatterngraphsfortheefficientcomputationofitsnumberofindependentsets
AT bellopedro basicpatterngraphsfortheefficientcomputationofitsnumberofindependentsets
AT contrerasmeliza basicpatterngraphsfortheefficientcomputationofitsnumberofindependentsets

Ejemplares similares