Department of Information Science, University of Tokyo
抄録
This paper proposes a unified approach by means of the binary decision diagram, BDD in short, to solve #P-hand problems of counting the number of paths between two terminals in undirected and directed graphs. Our approach provides algorithms running in O (2O (√n) ) time for typical planar graphs such as grid graphs. In fact, for any class of graphs having a good elimination ordering, this paradigm provides efficient solutions.
内容記述
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
雑誌名
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Counting the Number of Paths in a Graph via BDDs
Counting the Number of Paths in a Graph via BDDs 1997.pdf
(635.49KB)
