@InProceedings{Yamanaka:Horiyama:Uno:Wasa:CCCG2018,
  author    = "Katsuhisa Yamanaka and Takashi Horiyama and Takeaki Uno and Kunihiro Wasa",
  title     = "Ladder-Lottery Realization",
  booktitle = "Proceedings of the 30th Canadian Conference on Computational Geometry, (CCCG 2018), University of Manitoba, Winnipeg, Manitoba, Canada, August 8-10, 2018",
  pages     = "61--67",
  year      = "2018",
   abstract= "A ladder lottery of a permutation $\pi = (p_1,p_2,\ldots ,p_n)$ is a network with $n$ vertical lines and zero or more horizontal lines each of which connects two consecutive vertical lines. The top ends and the bottom ends of the vertical lines correspond to the identity permutation and $\pi$, respectively. Each horizontal line corresponds to an intersection of two vertical lines. Suppose that we are given a permutation $\pi$ of $[n]=\{1,2,\ldots ,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 $\pi$ 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.", 
  url       = "http://www.cs.umanitoba.ca/\backslash{}%7Ecccg2018/papers/session2A-p3.pdf",
  note = "Acceptance ratio = 45/65", 
}

{"_id":"fsRzkmBQb8BrCsw3B","bibbaseid":"yamanaka-horiyama-uno-wasa-ladderlotteryrealization-2018","authorIDs":["552f686310c2c096480000c9"],"author_short":["Yamanaka, K.","Horiyama, T.","Uno, T.","Wasa, K."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Katsuhisa"],"propositions":[],"lastnames":["Yamanaka"],"suffixes":[]},{"firstnames":["Takashi"],"propositions":[],"lastnames":["Horiyama"],"suffixes":[]},{"firstnames":["Takeaki"],"propositions":[],"lastnames":["Uno"],"suffixes":[]},{"firstnames":["Kunihiro"],"propositions":[],"lastnames":["Wasa"],"suffixes":[]}],"title":"Ladder-Lottery Realization","booktitle":"Proceedings of the 30th Canadian Conference on Computational Geometry, (CCCG 2018), University of Manitoba, Winnipeg, Manitoba, Canada, August 8-10, 2018","pages":"61–67","year":"2018","abstract":"A ladder lottery of a permutation $π= (p_1,p_2,…,p_n)$ is a network with $n$ vertical lines and zero or more horizontal lines each of which connects two consecutive vertical lines. The top ends and the bottom ends of the vertical lines correspond to the identity permutation and $\\pi$, respectively. Each horizontal line corresponds to an intersection of two vertical lines. Suppose that we are given a permutation $\\pi$ 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 $\\pi$ 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.","url":"http://www.cs.umanitoba.ca/\\backslash%7Ecccg2018/papers/session2A-p3.pdf","note":"Acceptance ratio = 45/65","bibtex":"@InProceedings{Yamanaka:Horiyama:Uno:Wasa:CCCG2018,\n author = \"Katsuhisa Yamanaka and Takashi Horiyama and Takeaki Uno and Kunihiro Wasa\",\n title = \"Ladder-Lottery Realization\",\n booktitle = \"Proceedings of the 30th Canadian Conference on Computational Geometry, (CCCG 2018), University of Manitoba, Winnipeg, Manitoba, Canada, August 8-10, 2018\",\n pages = \"61--67\",\n year = \"2018\",\n abstract= \"A ladder lottery of a permutation $\\pi = (p_1,p_2,\\ldots ,p_n)$ is a network with $n$ vertical lines and zero or more horizontal lines each of which connects two consecutive vertical lines. The top ends and the bottom ends of the vertical lines correspond to the identity permutation and $\\pi$, respectively. Each horizontal line corresponds to an intersection of two vertical lines. Suppose that we are given a permutation $\\pi$ of $[n]=\\{1,2,\\ldots ,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 $\\pi$ 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.\", \n url = \"http://www.cs.umanitoba.ca/\\backslash{}%7Ecccg2018/papers/session2A-p3.pdf\",\n note = \"Acceptance ratio = 45/65\", \n}\n","author_short":["Yamanaka, K.","Horiyama, T.","Uno, T.","Wasa, K."],"key":"Yamanaka:Horiyama:Uno:Wasa:CCCG2018","id":"Yamanaka:Horiyama:Uno:Wasa:CCCG2018","bibbaseid":"yamanaka-horiyama-uno-wasa-ladderlotteryrealization-2018","role":"author","urls":{"Paper":"http://www.cs.umanitoba.ca/\\backslash%7Ecccg2018/papers/session2A-p3.pdf"},"downloads":0},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/KunihiroWASA/publications_bib/master/publications.bib","creationDate":"2019-08-01T03:02:18.881Z","downloads":0,"keywords":[],"search_terms":["ladder","lottery","realization","yamanaka","horiyama","uno","wasa"],"title":"Ladder-Lottery Realization","year":2018,"dataSources":["G5knAh5sDHZjd7TY8"]}