| Item type |
SIG Technical Reports(1) |
| 公開日 |
2018-11-05 |
| タイトル |
|
|
タイトル |
The Complexity of Ladder-Lottery Realization Problem |
| タイトル |
|
|
言語 |
en |
|
タイトル |
The Complexity of Ladder-Lottery Realization Problem |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
Iwate University |
| 著者所属 |
|
|
|
Saitama University |
| 著者所属 |
|
|
|
National Institute of Informatics |
| 著者所属 |
|
|
|
National Institute of Informatics |
| 著者所属(英) |
|
|
|
en |
|
|
Iwate University |
| 著者所属(英) |
|
|
|
en |
|
|
Saitama University |
| 著者所属(英) |
|
|
|
en |
|
|
National Institute of Informatics |
| 著者所属(英) |
|
|
|
en |
|
|
National Institute of Informatics |
| 著者名 |
Katsuhisa, Yamanaka
Takashi, Horiyama
Takeaki, Uno
Kunihiro, Wasa
|
| 著者名(英) |
Katsuhisa, Yamanaka
Takashi, Horiyama
Takeaki, Uno
Kunihiro, Wasa
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
A ladder lottery of a permutation π = (p1, p2,...,pn) is a network with n vertical lines and zero or more horizontal lines each of which connects exactly two consecutive vertical lines. The top ends and the bottom ends of the vertical lines correspond to the identity permutation and π, respectively. Each horizontal line corresponds to an intersection of two vertical lines. Suppose that we are given a permutation π of [n] = {1, 2,...,n} and a multi-set S of intersections each of which is a pair of elements in [n]. Then Ladder-Lottery Realization problem asks whether or not there is a ladder-lottery of π in which each intersection in S appears exactly once. We show that Ladder-Lottery Realization problem is NP-complete. We also present some positive results of Ladder-Lottery Realization and its variant. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
A ladder lottery of a permutation π = (p1, p2,...,pn) is a network with n vertical lines and zero or more horizontal lines each of which connects exactly two consecutive vertical lines. The top ends and the bottom ends of the vertical lines correspond to the identity permutation and π, respectively. Each horizontal line corresponds to an intersection of two vertical lines. Suppose that we are given a permutation π of [n] = {1, 2,...,n} and a multi-set S of intersections each of which is a pair of elements in [n]. Then Ladder-Lottery Realization problem asks whether or not there is a ladder-lottery of π in which each intersection in S appears exactly once. We show that Ladder-Lottery Realization problem is NP-complete. We also present some positive results of Ladder-Lottery Realization and its variant. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2018-AL-170,
号 1,
p. 1-6,
発行日 2018-11-05
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL18170001.pdf (706.1 kB)
