| Presentation | 2011-12-16 Relationship Between Coding Theory and Counting Perfect Matchings Taisuke IZUMI, Tadashi WADAYAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Counting perfect matchings is known as one of the hard problems to obtain exact results, which is proven to be #P-complete even if we restrict input graphs to 3-regular bipartite ones. In this paper, we show a polynomial-space O^^～(2^<5n/12>)-time algorithm to compute the exact number of perfect matchings for any 3-regular bipartite graph. This algorithm is derived from the coding-theoretic perspective of the cut and circuit spaces of the input graph. We can interpret their relationship to the duality of linear codes associated with two spaces, which yields the reduction of counting perfect matchings to the computation of cut-space weight distribution. Our algorithm is obtained by designing a faster algorithm for calculating that distribution. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Counting perfect matchings / exponential algorithm / coding theory / linear codes / MacWilliams identity |
| Paper # | COMP2011-37 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2011/12/9(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Relationship Between Coding Theory and Counting Perfect Matchings |
| Sub Title (in English) | |
| Keyword(1) | Counting perfect matchings |
| Keyword(2) | exponential algorithm |
| Keyword(3) | coding theory |
| Keyword(4) | linear codes |
| Keyword(5) | MacWilliams identity |
| 1st Author's Name | Taisuke IZUMI |
| 1st Author's Affiliation | Nagoya Institute of Technology() |
| 2nd Author's Name | Tadashi WADAYAMA |
| 2nd Author's Affiliation | Nagoya Institute of Technology |
| Date | 2011-12-16 |
| Paper # | COMP2011-37 |
| Volume (vol) | vol.111 |
| Number (no) | 360 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |