| 03 |
Ask me anything about network structureIndexing graph structure with decision diagrams 
|
|---|
We developed a new substructure index called the zero-suppressed sentential decision diagram (ZSDD) and efficient algorithms with which to construct it. A substructure index is a compact representation of network substructures. With it, we can count and find exponentially many substructures in time linear to the index size. Since ZSDD is generally smaller than similar data structures, we can solve network-related problems much faster. For example, we can count more than 100 million network routes within a second using ZSDD. Our algorithm can solve a wide range of problems on real-world networks like communication networks, traffic networks, and power grids. Therefore, it will make society more efficient by finding better solutions to network-related problems.
[1] M. Nishino, N. Yasuda, S. Minato, M. Nagata, “Zero-suppressed Sentential Decision Diagrams,” in Proc. 30th AAAI Conference on Artificial Intelligence (AAAI 16), 2016.
[2] M. Nishino, N. Yasuda, S. Minato, M. Nagata, “Compiling Graph Substructures into Sentential Decision Diagrams,” in Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 17), 2017.
[3] Y. Nakahata, M. Nishino, J. Kawahara, S. Minato, “Enumerating All Subgraphs Under Given Constraints using Zero-suppressed Sentential Decision Diagrams,” in Proc. 18th Symposium on Experimental Algorithms (SEA 2020), 2020.
Masaaki Nishino / Linguistic Intelligence Research Group, Innovative Communication Laboratory
Email: cs-openhouse-ml@hco.ntt.co.jp