| Presentation | 2015-09-01 Enumerating and Indexing Walks Between Any Pair of Vertices Hiroshi Aoki, Norihito Yasuda, Shin-ichi Minato, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper presents a method for enumerating and indexing all the walks between any two points in a given graph. It is known that paths, which contain each vertex at most one time, can be enumerated and indexed with a Zero-Suppressed Binary Decision Diagram (ZDD) based methods. Since a ZDD efficiently handles a family of sets, the methods naturally represents a set of paths by regarding each path as a set of edges. However, ZDDs are hard to represent walks, which may contain same vertices more than one time. We consider representing walks by SeqBDD, which is a data structure that compactly represents a set of sequences. It is also well known that the numbers of walks between any two vertices can be calculated by a series of multiplication of an adjacent matrix. We propose an extension of an adjacent matrix called SeqBDD matrix. Instead of usual numbers, non-zero elements in a SeqBDD matrix are filled with SeqBDDs. We specify that multiplication of the SeqBDD matrix can enumerate walks and index them as SeqBDDs. We also present some operations such as narrowing down the resulting SeqBDDs and counting with some experimental results. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | SeqBDD / Walk |
| Paper # | COMP2015-21 |
| Date of Issue | 2015-08-25 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2015/9/1(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Koichi Wada(Hosei Univ.) |
| Vice Chair | Toshimitsu Masuzawa(Osaka Univ.) |
| Secretary | Toshimitsu Masuzawa(Hiroshima Univ.) |
| Assistant | |
| 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) | Enumerating and Indexing Walks Between Any Pair of Vertices |
| Sub Title (in English) | |
| Keyword(1) | SeqBDD |
| Keyword(2) | Walk |
| 1st Author's Name | Hiroshi Aoki |
| 1st Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| 2nd Author's Name | Norihito Yasuda |
| 2nd Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| 3rd Author's Name | Shin-ichi Minato |
| 3rd Author's Affiliation | Hokkaido University(Hokkaido Univ.) |
| Date | 2015-09-01 |
| Paper # | COMP2015-21 |
| Volume (vol) | vol.115 |
| Number (no) | COMP-205 |
| Page | pp.pp.35-39(COMP), |
| #Pages | 5 |
| Date of Issue | 2015-08-25 (COMP) |