Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875616 | Theoretical Computer Science | 2018 | 10 Pages |
Abstract
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(nMn) time complexity, where Mn 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 with n vertices.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Átila A. Jones, Fábio Protti, Renata R. Del-Vecchio,