Cograph generation with linear delay
| Autor: | Jones, Átila A., Protti, Fábio, Del-Vecchio, Renata R. |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Theoretical Computer Science Volume 713, 22 February 2018, Pages 1-10 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.tcs.2017.12.037 |
| Popis: | Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with $n$ vertices, based on the generation of cotrees. The delay of our algorithm (time spent between two consecutive outputs) is $O(n)$. The time needed to generate the first output is also $O(n)$, which gives an overall $O(n\,M_n)$ time complexity, where $M_n$ is the number of unlabeled cographs with $n$ vertices. The algorithm avoids the generation of duplicates (isomorphic outputs) and produces, as a by-product, a linear ordering of unlabeled cographs wih $n$ vertices. Comment: 22 pages, 3 figures. Submitted to Theoretical Computer Science |
| Databáze: | arXiv |
| Externí odkaz: |
|