Art

J-GLOBAL ID：201802242532220093   Reference number：18A2209515

The Complexity of Ladder-Lottery Realization Problem

Ladder-Lottery実現問題の複雑さ

Author (4)： YAMANAKA Katsuhisa (Iwate Univ., Iwate, JPN) ,  HORIYAMA Takashi (Saitama Univ., Saitama, JPN) ,  UNO Takeaki (National Inst. Informatics, Tokyo, JPN) ,  WASA Kunihiro (National Inst. Informatics, Tokyo, JPN)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 118  Issue： 296(MSS2018 37-53)  Page： 1-6  Publication year： Nov. 05, 2018 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *problem ,  *computational complexity ,  *NP hard ,  ladder approximation ,  programming language ,  pleasure ,  application program ,  permutation
Semi thesaurus term： *Ladder-Lottery実現問題 ,  *computational complexity ,  ladder diagram ,  Puzzle ,  gadget

JST classification (1)： Theory of computation  (JB02000A)

Reference (12)：

• É. Bonnet, T. Miltzow, and P. Rzążewski. Complexity of token swapping and its variants. Algorithmica, pages 1-27, Oct 2017.
• M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.
• T. Horiyama, K. Wasa, and K. Yamanaka. Reconfiguring optimal ladder lotteries. In Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pages 217-224, May 2017.
• J. Kawahara, T. Saitoh, and R. Yoshinaka. The time complexity of the token swapping problem and its parallel variants. In Proceeding of The 11th International Conference and Workshops on Algorithms and Computation, volume 10167 of Lecture Notes in Computer Science, pages 448-459,2017.
• J. Kawahara, T. Saitoh, R. Yoshinaka, and S. Minato. Counting primitive sorting networks by πdds. Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-11-54,2011.

Terms in the title (2)： 問題 ,  複雑さ