Efficient Enumeration of All Ladder Lotteries with k Bars

スポンサーリンク

概要

• 論文の詳細を見る

• A ladder lottery, known as the "Amidakuji" in Japan, is a network with n vertical lines and many horizontal lines each of which connects two consecutive vertical lines. Each ladder lottery corresponds to a permutation. Ladder lotteries are frequently used as natural models in many areas. Given a permutation π, an algorithm to enumerate all ladder lotteries of π with the minimum number of horizontal lines are known. In this paper, given a permutation π and an integer k, we design an algorithm to enumerate all ladder lotteries of π with exactly k horizontal lines.

• 一般社団法人情報処理学会の論文
• 2009-09-08

著者

• Katsuhisa Yamanaka

  Graduate School of Information Systems, University of Electro-communications.

• Katsuhisa Yamanaka

  Graduate School Of Information Systems University Of Electro-communications.

関連論文

• Enumerating All Rooted Trees Including k Leaves
• Computational Complexities of University Interview Timetabling
• Random Generation and Enumeration of Proper Interval Graphs
• Efficient Enumeration of All Ladder Lotteries with k Bars
• Efficient Enumeration of All Pseudoline Arrangements
• A Compact Encoding of Rectangular Drawings with Edge Lengths
• Approximating the path-distance-width for k-cocomparability graphs
• Coding Ladder Lotteries

スポンサーリンク