Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Rerouting Planar Curves and Disjoint Paths. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 81:1-81:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ito_et_al:LIPIcs.ICALP.2023.81, author = {Ito, Takehiro and Iwamasa, Yuni and Kakimura, Naonori and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta}, title = {{Rerouting Planar Curves and Disjoint Paths}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {81:1--81:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.81}, URN = {urn:nbn:de:0030-drops-181339}, doi = {10.4230/LIPIcs.ICALP.2023.81}, annote = {Keywords: Disjoint paths, combinatorial reconfiguration, planar graphs} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 82:1-82:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ito_et_al:LIPIcs.ICALP.2023.82, author = {Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio}, title = {{Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {82:1--82:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.82}, URN = {urn:nbn:de:0030-drops-181344}, doi = {10.4230/LIPIcs.ICALP.2023.82}, annote = {Keywords: Graph associahedra, combinatorial shortest path, NP-hardness, polymatroids} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Reconfiguration of Colorings in Triangulations of the Sphere. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 43:1-43:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ito_et_al:LIPIcs.SoCG.2023.43, author = {Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta}, title = {{Reconfiguration of Colorings in Triangulations of the Sphere}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {43:1--43:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.43}, URN = {urn:nbn:de:0030-drops-178936}, doi = {10.4230/LIPIcs.SoCG.2023.43}, annote = {Keywords: Graph coloring, Triangulation of the sphere, Combinatorial reconfiguration} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Shortest Reconfiguration of Perfect Matchings via Alternating Cycles. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 61:1-61:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{ito_et_al:LIPIcs.ESA.2019.61, author = {Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Okamoto, Yoshio}, title = {{Shortest Reconfiguration of Perfect Matchings via Alternating Cycles}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {61:1--61:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.61}, URN = {urn:nbn:de:0030-drops-111823}, doi = {10.4230/LIPIcs.ESA.2019.61}, annote = {Keywords: Matching, Combinatorial reconfiguration, Alternating cycles, Combinatorial shortest paths} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Takashi Ishizuka and Naoyuki Kamiyama. On the Complexity of Stable Fractional Hypergraph Matching. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 11:1-11:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{ishizuka_et_al:LIPIcs.ISAAC.2018.11, author = {Ishizuka, Takashi and Kamiyama, Naoyuki}, title = {{On the Complexity of Stable Fractional Hypergraph Matching}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {11:1--11:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.11}, URN = {urn:nbn:de:0030-drops-99590}, doi = {10.4230/LIPIcs.ISAAC.2018.11}, annote = {Keywords: fractional hypergraph matching, stable matching, PPAD-completeness} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Naonori Kakimura, Naoyuki Kamiyama, and Kenjiro Takazawa. The b-Branching Problem in Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{kakimura_et_al:LIPIcs.MFCS.2018.12, author = {Kakimura, Naonori and Kamiyama, Naoyuki and Takazawa, Kenjiro}, title = {{The b-Branching Problem in Digraphs}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {12:1--12:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.12}, URN = {urn:nbn:de:0030-drops-95948}, doi = {10.4230/LIPIcs.MFCS.2018.12}, annote = {Keywords: Greedy Algorithm, Packing, Matroid Intersection, Sparsity Matroid, Arborescence} }
Feedback for Dagstuhl Publishing