JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/9176

タイトル: Efficient Enumeration of All Ladder Lotteries and Its Application
著者: Yamanaka, Katsuhisa
Nakano, Shin-ichi
Matsui, Yasuko
Uehara, Ryuhei
Nakada, Kento
キーワード: Enumeration algorithm
Family tree
Ladder lottery
Pseudoline arrangement
発行日: 2010-01-13
出版者: Elsevier
誌名: Theoretical Computer Science
巻: 411
号: 16-18
開始ページ: 1714
終了ページ: 1722
DOI: 10.1016/j.tcs.2010.01.002
抄録: A ladder lottery, known as “Amidakuji” in Japan, is a common way to choose a permutation randomly. A ladder lottery L corresponding to a given permutation π is optimal if L has the minimum number of horizontal lines among the ladder lotteries corresponding to π. 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. By setting π=(n,n−1,…,1), the algorithm enumerates all arrangements of n pseudolines efficiently. By implementing the algorithm we compute the number of arrangements of n pseudolines for each n≤11.
Rights: NOTICE: This is the author’s version of a work accepted for publication by Elsevier. Changes resulting from the publishing process, including peer review, editing, corrections, structural formatting and other quality control mechanisms, may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada, Theoretical Computer Science, 411(16-18), 2010, 1714-1722, http://dx.doi.org/10.1016/j.tcs.2010.01.002
URI: http://hdl.handle.net/10119/9176
資料タイプ: author
出現コレクション:b10-1. 雑誌掲載論文 (Journal Articles)

このアイテムのファイル:

ファイル 記述 サイズ形式
15049.pdf162KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係