| Presentation | 2019-09-02 Enumeration of Chordal and Interval Subgraphs Using Binary Decision Diagrams Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, Ryo Yoshinaka, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This research proposes algorithms that construct compressed datastructures, called zero-suppressed binary decision diagrams, which represent the sets of all the chordal and interval subgraphsof a given graph, respectively. The proposed algorithms are extensions of an existing framework, called frontier-based search, to construct zero-suppressedbinary decision diagrams for the set of subgraphs satisfying specified conditions. By numerical experiments, the proposed algorithms are comparedwith existing reverse search-based algorithms, which output solutions one by one. This research has been published atSpecial Event on Analysis of Experimental Algorithms (SEA^2 2019). |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Graph algorithm / Graph enumeration / Decision diagram / Frontier-based search / Interval graph / Chordal graph |
| Paper # | COMP2019-16 |
| Date of Issue | 2019-08-26 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2019/9/2(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Tsushima Campus, Okayama University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Enumeration of Chordal and Interval Subgraphs Using Binary Decision Diagrams |
| Sub Title (in English) | |
| Keyword(1) | Graph algorithm |
| Keyword(2) | Graph enumeration |
| Keyword(3) | Decision diagram |
| Keyword(4) | Frontier-based search |
| Keyword(5) | Interval graph |
| Keyword(6) | Chordal graph |
| 1st Author's Name | Jun Kawahara |
| 1st Author's Affiliation | Nara Institute of Science and Technology(NAIST) |
| 2nd Author's Name | Toshiki Saitoh |
| 2nd Author's Affiliation | Kyushu Institute of Technology(Kyutech) |
| 3rd Author's Name | Hirofumi Suzuki |
| 3rd Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| 4th Author's Name | Ryo Yoshinaka |
| 4th Author's Affiliation | Tohoku University(Tohoku Univ.) |
| Date | 2019-09-02 |
| Paper # | COMP2019-16 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-191 |
| Page | pp.pp.33-33(COMP), |
| #Pages | 1 |
| Date of Issue | 2019-08-26 (COMP) |