2023-12-02T04:54:12Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002256622023-05-02T15:00:00Z01164:02592:11085:11247
Enumeration of Non-isomorphic Unordered Trees with Degree Sequence ConstraintsEnumeration of Non-isomorphic Unordered Trees with Degree Sequence Constraintsenghttp://id.nii.ac.jp/1001/00225553/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=225662&item_no=1&attribute_id=1&file_no=1Copyright (c) 2023 by the Information Processing Society of JapanNTT Communication Science Laboratories, NTT CorporationHokkaido UniversityNagoya UniversityOchanomizu UniversityHokkaido UniversityHousei UniversityShuhei, DenzumiTakashi, HoriyamaKazuhiro, KuritaAtsuki, NagaoKazuhisa, SetoKunihiro, WasaEnumerating 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-19311162023-05-032188-85662023-04-20