We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Enumerating Tree-Like Graphs and Polymer Topologies with a Given Cycle Rank.
- Authors
Azam, Naveed Ahmed; Shurbevski, Aleksandar; Nagamochi, Hiroshi
- Abstract
Cycle rank is an important notion that is widely used to classify, understand, and discover new chemical compounds. We propose a method to enumerate all non-isomorphic tree-like graphs of a given cycle rank with self-loops and no multiple edges. To achieve this, we develop an algorithm to enumerate all non-isomorphic rooted graphs with the required constraints. The idea of our method is to define a canonical representation of rooted graphs and enumerate all non-isomorphic graphs by generating the canonical representation of rooted graphs. An important feature of our method is that for an integer n ≥ 1 , it generates all required graphs with n vertices in O (n) time per graph and O (n) space in total, without generating invalid intermediate structures. We performed some experiments to enumerate graphs with a given cycle rank from which it is evident that our method is efficient. As an application of our method, we can generate tree-like polymer topologies of a given cycle rank with self-loops and no multiple edges.
- Subjects
REPRESENTATIONS of graphs; ALGORITHMS; TOPOLOGY; POLYMERS
- Publication
Entropy, 2020, Vol 22, Issue 11, p1295
- ISSN
1099-4300
- Publication type
Article
- DOI
10.3390/e22111295