| Presentation | 2009-03-02 Efficient Enumeration of All Ladder Lotteries Katsuhisa YAMANAKA, Shin-ichi NAKANO, Yasuko MATSUI, Ryuhei UEHARA, Kento NAKADA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A ladder lottery, known as the "Amidakuji" in Japan, is a common way to choose a random permutation. Given a permutation, a ladder lottery is optimal if it consists of the minimum number of horizontal-lines. In this paper we show that for any two optimal ladder lotteries L_1 and L_2 of a permutation, there exists a sequence of local modifications which transforms L_1 into L_2. We also give an algorithm to enumerate all optimal ladder lotteries of a given permutation. Our algorithm has an application in algebraic combinatorics. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | algorithm / ladder lottery / enumeration / family tree |
| Paper # | COMP2008-56 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2009/2/23(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 | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Efficient Enumeration of All Ladder Lotteries |
| Sub Title (in English) | |
| Keyword(1) | algorithm |
| Keyword(2) | ladder lottery |
| Keyword(3) | enumeration |
| Keyword(4) | family tree |
| 1st Author's Name | Katsuhisa YAMANAKA |
| 1st Author's Affiliation | Graduate School of Information Systems, The University of Electro-Communications() |
| 2nd Author's Name | Shin-ichi NAKANO |
| 2nd Author's Affiliation | Graduate School of Computer Science, Gunma University |
| 3rd Author's Name | Yasuko MATSUI |
| 3rd Author's Affiliation | Department of Mathematical Sciences, Tokai University |
| 4th Author's Name | Ryuhei UEHARA |
| 4th Author's Affiliation | School of Information Science, Japan Advanced Institute of Science and Technology |
| 5th Author's Name | Kento NAKADA |
| 5th Author's Affiliation | Research Institute for Mathematical Sciences, Kyoto University |
| Date | 2009-03-02 |
| Paper # | COMP2008-56 |
| Volume (vol) | vol.108 |
| Number (no) | 443 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |