Article ID Journal Published Year Pages File Type
6875616 Theoretical Computer Science 2018 10 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,