Fast Compilation of s-t Paths on a Graph for Counting and Enumeration

Norihito Yasuda, Teruji Sugaya, Shin-Ichi Minato
Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, PMLR 73:129-140, 2017.

Abstract

In this paper, we propose a new method to compile $s$-$t$ simple paths on a graph using a new compilation method called merging frontier based search. Recently, Nishino et al. proposed a top-down construction algorithm, which compiles $s$-$t$ simple paths into a Zero-suppressed SDD (ZSDD), and they showed that this method is more efficient than simpath by Knuth. However, since the method of Nishino et al. uses ZSDD as a tractable representation, it requires complicated steps for compilation. In this paper, we propose z-st-d-DNNF, which is a super set of ZSDD. By using this method instead of ZSDD, we show that more efficient $s$-$t$ simple paths compilation can be realized.

Cite this Paper

BibTeX
@InProceedings{pmlr-v73-teruji-sugaya17a, title = {Fast Compilation of s-t Paths on a Graph for Counting and Enumeration}, author = {Yasuda, Norihito and Sugaya, Teruji and Minato, Shin-Ichi}, booktitle = {Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks}, pages = {129--140}, year = {2017}, editor = {Hyttinen, Antti and Suzuki, Joe and Malone, Brandon}, volume = {73}, series = {Proceedings of Machine Learning Research}, month = {20--22 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v73/teruji-sugaya17a/teruji-sugaya17a.pdf}, url = {https://proceedings.mlr.press/v73/teruji-sugaya17a.html}, abstract = {In this paper, we propose a new method to compile $s$-$t$ simple paths on a graph using a new compilation method called merging frontier based search. Recently, Nishino et al. proposed a top-down construction algorithm, which compiles $s$-$t$ simple paths into a Zero-suppressed SDD (ZSDD), and they showed that this method is more efficient than simpath by Knuth. However, since the method of Nishino et al. uses ZSDD as a tractable representation, it requires complicated steps for compilation. In this paper, we propose z-st-d-DNNF, which is a super set of ZSDD. By using this method instead of ZSDD, we show that more efficient $s$-$t$ simple paths compilation can be realized. } }
Endnote
%0 Conference Paper %T Fast Compilation of s-t Paths on a Graph for Counting and Enumeration %A Norihito Yasuda %A Teruji Sugaya %A Shin-Ichi Minato %B Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks %C Proceedings of Machine Learning Research %D 2017 %E Antti Hyttinen %E Joe Suzuki %E Brandon Malone %F pmlr-v73-teruji-sugaya17a %I PMLR %P 129--140 %U https://proceedings.mlr.press/v73/teruji-sugaya17a.html %V 73 %X In this paper, we propose a new method to compile $s$-$t$ simple paths on a graph using a new compilation method called merging frontier based search. Recently, Nishino et al. proposed a top-down construction algorithm, which compiles $s$-$t$ simple paths into a Zero-suppressed SDD (ZSDD), and they showed that this method is more efficient than simpath by Knuth. However, since the method of Nishino et al. uses ZSDD as a tractable representation, it requires complicated steps for compilation. In this paper, we propose z-st-d-DNNF, which is a super set of ZSDD. By using this method instead of ZSDD, we show that more efficient $s$-$t$ simple paths compilation can be realized.
APA
Yasuda, N., Sugaya, T. & Minato, S.. (2017). Fast Compilation of s-t Paths on a Graph for Counting and Enumeration. Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, in Proceedings of Machine Learning Research 73:129-140 Available from https://proceedings.mlr.press/v73/teruji-sugaya17a.html.

Related Material