Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams

• Item type: SIG Technical Reports(1)
• 公開日: 2018-03-01
• タイトル: Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams
• タイトル / 言語: en
• タイトル: Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Science and Engineering, Saitama University
• 著者所属: Graduate School of Science and Engineering, Saitama University
• 著者所属: Faculty of Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Saitama University
• 著者名: Takashi, Horiyama; Masahiro, Miyasaka; Riku, Sasaki
• 著者名(英): Takashi, Horiyama; Masahiro, Miyasaka; Riku, Sasaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In this paper, we focus on the isomorphism elimination. More precisely, our problem is as follows : Given a graph G with labeled edges and a family F of its subgraphs, we extract all automorphisms AutG = {π1, π2,...,} on the given graph, define the lexicographically largest subgraph for each set of the mutually isomorphic subgraphs on each automorphism πi, and select the lexicographically largest subgraphs on any of the automorphisms. In this paper, both of the given and resulting families of subgraphs are in the form of ZDDs, and the computation are performed on ZDDs. Experimental results show that the proposed method is 300 times faster and 3,000 times less memory than the conventional method in the best case.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we focus on the isomorphism elimination. More precisely, our problem is as follows : Given a graph G with labeled edges and a family F of its subgraphs, we extract all automorphisms AutG = {π1, π2,...,} on the given graph, define the lexicographically largest subgraph for each set of the mutually isomorphic subgraphs on each automorphism πi, and select the lexicographically largest subgraphs on any of the automorphisms. In this paper, both of the given and resulting families of subgraphs are in the form of ZDDs, and the computation are performed on ZDDs. Experimental results show that the proposed method is 300 times faster and 3,000 times less memory than the conventional method in the best case.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-167, 号 7, p. 1-5, 発行日 2018-03-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会