Presentation information

Organized Session

Organized Session » OS-17

[2N5-OS-17b] OS-17 (2)

Wed. Jun 10, 2020 3:50 PM - 5:30 PM Room N (jsai2020online-14)

宋 剛秀(神戸大学)、沖本 天太(神戸大学)

4:30 PM - 4:50 PM

[2N5-OS-17b-03] Construction of BDD for Indexing Vertex Separators between All Vertex Pairs of Graphs

〇Masahiro Takahashi1, Jun Kawahara1, Shin-ichi Minato1 (1. Graduate School of Informatics, Kyoto University)

Keywords:decision diagram, enumeration, graph algorithm

It is fundamental to consider vertex separators of a given graph. In this article, we propose an algorithm that, when an undirected graph is given as input, indexes all vertex separators of all vertex pairs in a form that can be easily used later. In this article, we first formulate the indexing of vertex separators as a dynamic programming problem. Then by using a data structure called BDD for indexing, we aim for an efficient algorithm. In the experiments, the proposed algorithm was applied to square lattice graphs, which are graphs with a regular structure, and randomly generated graphs. As a result, it was found that the proposed algorithm operates fast especially on graphs with regular structures and graphs with dense edges. We also show that by slightly changing the details of the proposed algorithm, it is possible to index vertex sets similar to vertex separators, such as those which cause d-separation in Bayesian networks.

Authentication for paper PDF access

A password is required to view paper PDFs. If you are a registered participant, please log on the site from Participant Log In.
You could view the PDF with entering the PDF viewing password bellow.