http://swrc.ontoware.org/ontology#TechnicalReport
Enumeration of Non-isomorphic Unordered Trees with Degree Sequence Constraints
en
NTT Communication Science Laboratories, NTT Corporation
Hokkaido University
Nagoya University
Ochanomizu University
Hokkaido University
Housei University
Shuhei Denzumi
Takashi Horiyama
Kazuhiro Kurita
Atsuki Nagao
Kazuhisa Seto
Kunihiro Wasa
Enumerating non-isomorphic rooted ordered trees satisfying the given number of vertices and edges has been studied with several constraints. Especially, efficient enumeration algorithms have been developed for basic constraints such as the number of leaves and diameter constraints. However, the total number of ordered trees is huge, and even if an efficient enumeration algorithm is given, it is not easy to enumerate solutions. One way to solve this problem is to reduce the number of solutions. Thus, we give an algorithm to enumerate non-isomorphic trees instead of rooted ordered trees. Furthermore, we give an efficient algorithm to enumerate non-isomorphic trees satisfying the degree sequence constraints.
Enumerating non-isomorphic rooted ordered trees satisfying the given number of vertices and edges has been studied with several constraints. Especially, efficient enumeration algorithms have been developed for basic constraints such as the number of leaves and diameter constraints. However, the total number of ordered trees is huge, and even if an efficient enumeration algorithm is given, it is not easy to enumerate solutions. One way to solve this problem is to reduce the number of solutions. Thus, we give an algorithm to enumerate non-isomorphic trees instead of rooted ordered trees. Furthermore, we give an efficient algorithm to enumerate non-isomorphic trees satisfying the degree sequence constraints.
AN1009593X
研究報告アルゴリズム（AL）
2023-AL-193
11
1-6
2023-05-03
2188-8566