2026-05-12T02:49:05Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00186563 2025-01-20T02:32:49Z 1164:2592:9368:9433

Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams Isomorphism Elimination by Zero-Suppressed Binary Decision Diagrams Takashi, Horiyama Masahiro, Miyasaka Riku, Sasaki Takashi, Horiyama Masahiro, Miyasaka Riku, Sasaki 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. 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. 情報処理学会 2018-03-01 eng technical report https://ipsj.ixsq.nii.ac.jp/records/186563 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2018-AL-167 7 1 5 https://ipsj.ixsq.nii.ac.jp/record/186563/files/IPSJ-AL18167007.pdf application/pdf 626.7 kB 2020-03-01