ポリアの数え上げに基づく非同型な塗分けの索引化

• Item type: SIG Technical Reports(1)
• 公開日: 2019-02-26
• タイトル: ポリアの数え上げに基づく非同型な塗分けの索引化
• タイトル / 言語: en
• タイトル: Indexing Nonisomorphic Graph Colorings Based on the Pólya's Theorem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 埼玉大学理工学研究科
• 著者所属: 埼玉大学理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Saitama University
• 著者名: 角野, 周平; 堀山, 貴史
• 著者名(英): Shuhei, Kadono; Takashi, Horiyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 自己同型群が与えられたときに，Pólya の数え上げを利用して非同型な塗分けの個数を数え上げることができる．また，2018 年に Horiyama らにより提案された同型除去の手法により，零抑制型二分決定グラフ (ZDD : Zero-suppressed Binary Decision Diagram) を利用して，自己同型群のもとで非同型な塗分けを列挙することもできる．この手法は，実行時間の観点からも，メモリ使用量の観点からも，従来手法よりも大幅に効率的であるが，結果の ZDD のサイズが大きい場合には，必然的にメモリ使用量も大きくなる．本研究では，自己同型群と整数aが与えられたときに，非同型な塗分けに番号付けを行い，索引番号 a の非同型な塗分けを求める問題を提案する．また，数え上げと列挙の両方の手法を利用して，非明示的に (つまり明示的に列挙することなく) 番号付けを行いこの問題を解くための手法を提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given an automorphism on a set, we can count the number of nonisomorphic colorings by the Pólya's counting theorem. We can also enumerate the nonisomorphic colorings on the automorphism by the isomorphism elimination method with ZDDs (Zero-suppressed Binary Decision Diagrams), which is proposed by Horiyama et al. in 2018. This method is more than 100 times efficient on the computation time and memory consumption than conventional methods. Unfortunately, however, the memory consumption becomes large in case the resulting ZDD is large. In this paper, we propose the following problem : Given an automorphism on a set and an integer a, we implicitly make an index on the nonisomorphic colorings, and generate the one with index a. We also propose an algorithm that solve this problem by implicitly making an index (without enumerating the nonisomorphic colorings). We utilize both of the techniques on counting and enumeration.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-172, 号 2, p. 1-8, 発行日 2019-02-26
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会