Research by Yoshio Okamoto

[Japanese|English]

Everything is listed in the reverse chronological order, namely the newer first.
Please respect the copyrights, and notice that the manuscripts here are different from the copies from the publishers.

Listed in Database: DBLP | Google Scholar Citations | MathSciNet | ORCID iD iconorcid.org/0000-0002-9826-7074

Contents

Interest

Refereed Papers in Journals

  1. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki,
    On reachable assignments under dichotomous preferences.
    Theoretical Computer Science 979 (2023) 114196.
    DOI:10.1016/j.tcs.2023.114196 Preprint available at arXiv.

  2. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki,
    Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams.
    ACM Transactions on Algorithms 19 (2023) Article No. 6, pp. 1--22.
    DOI:10.1145/3561302
    (Preprint available at arXiv.org)

  3. Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Parada, Daniel Perz, André van Renssen, and Birgit Vogtenhuber,
    Graphs with large total angular resolution.
    Theoretical Computer Science 943 (2023) 73--88. (Open Access)
    DOI:10.1016/j.tcs.2022.12.010

  4. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    A parameterized view to the robust recoverable base problem of matroids under structural uncertainty.
    Operations Research Letters 50 (2022) pp. 370-375.
    DOI:10.1016/j.orl.2022.05.001 (Open Access)

  5. Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Submodular reassignment problem for reallocating agents to tasks with synergy effects.
    Discrete Optimization 44 (2022) Article No. 100631.
    DOI:10.1016/j.disopt.2021.100631
    ( Manuscript: PDF; 544898 bytes)

  6. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Shortest reconfiguration of perfect matchings via alternating cycles.
    SIAM Journal on Discrete Mathematics 36 (2022) pp. 1102-1123.
    DOI:10.1137/20M1364370

  7. Luis Barba, Otfried Cheong, Michael Gene Dobbins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang, Takeshi Tokuyama, and Sander Verdonschot,
    Weight balancing on boundaries.
    Journal of Computational Geometry 13 (2022) pp. 1-12.
    DOI:10.20382/jocg.v13i1a1 (Open Access)

  8. Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Yushi Uno,
    Linear-time recognition of double-threshold graphs.
    Algorithmica 84 (2022) 1163-1181.
    DOI:10.1007/s00453-021-00921-9 (Open Access)
    (Preprint available at arXiv.org)

  9. Katsuhisa Yamanaka, David Avis, Takashi Horiyama, Yoshio Okamoto, Ryuhei Uehara, Tanami Yamauchi,
    Algorithmic Enumeration of Surrounding Polygons.
    Discrete Applied Mathematics 303 (2021) pp. 305-313.
    DOI:10.1016/j.dam.2020.03.034

  10. Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Algorithms for Gerrymandering Over Graphs.
    Theoretical Computer Science 868 (2021) 30-45.
    DOI:10.1016/j.tcs.2021.03.037

  11. Elena Arseneva, Man-Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen, Marcel Roeloffzen.
    Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain.
    Computational Geometry: Theory and Applications 92 (2021) 101685.
    DOI:10.1016/j.comgeo.2020.101685

  12. Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Tom C. van der Zanden.
    Subgraph Isomorphism on Graph Classes that Exclude a Substructure.
    Algorithmica 82 (2020) pp. 3566-3587.
    DOI:10.1007/s00453-020-00737-z

  13. Paz Carmi, Man Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, and Shakhar Smorodinsky,
    Balanced line separators of unit disk graphs.
    Computational Geometry: Theory and Applications 86 (2020) 101575.
    DOI:10.1016/j.comgeo.2019.101575

  14. Sang Won Bae, Yoshio Okamoto, and Chan-Su Shin,
    Area bounds of rectilinear polygons realized by angle sequences.
    Computational Geometry: Theory and Applications 83 (2019) 9-29.
    DOI:10.1016/j.comgeo.2019.05.004

  15. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Reconfiguration of Maximum-Weight b-Matchings in a Graph.
    Journal of Combinatorial Optimization 37 (2019) 454-464.
    DOI:10.1007/s10878-018-0289-3.

  16. Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno,
    Sequentially Swapping Colored Tokens on Graphs.
    Journal of Graph Algorithms and Applications 23 (2019) 3-27.
    Avaliable at the JGAA page.

  17. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Minimum-Cost b-Edge Dominating Sets on Trees.
    Algorithmica 81 (2019) 343-366.
    DOI:10.1007/s00453-018-0448-z.

  18. Sang Won Bae, Matias Korman, and Yoshio Okamoto,
    Computing the Geodesic Centers of a Polygonal Domain.
    Computational Geometry: Theory and Applications 77 (2019) 3-9.
    DOI:10.1016/j.comgeo.2015.10.009.
    (Preprint available as arXiv:1509.07214 [cs.CG], 2015.)

  19. Takashi Horiyama, Takashi Iizuka, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, and Yukiko Yamauchi,
    Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set.
    Journal of Information Processing 25 (2017) 708-715.
    DOI:10.2197/ipsjjip.25.708.

  20. Akinori Kawachi, Yoshio Okamoto, Keisuke Tanaka, and Kenji Yasunaga,
    General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction.
    The Computer Journal 60 (2017) 711-728.
    DOI:10.1093/comjnl/bxw094.

  21. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Efficient Stabilization of Cooperative Matching Games.
    Theoretical Computer Science 677 (2017) 69--82.
    DOI:10.1016/j.tcs.2017.03.020.

  22. Sang Won Bae, Matias Korman, Joseph Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang,
    Computing the L1 Geodesic Diameter and Center of a Polygonal Domain.
    Discrete & Computational Geometry 57 (2017) 674--701.
    DOI:10.1007/s00454-016-9841-z.

  23. Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh, Shuji Kijima, and Yoshio Okamoto,
    Extended formulations for sparsity matroids.
    Mathematical Programming 158 (2016) 565--574.
    DOI:10.1007/s10107-015-0936-8.
    (Preprint available as arXiv:1403.7272 [math.CO], 2014.)

  24. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström,
    On problems as hard as CNF-SAT.
    ACM Transactions on Algorithms 12(3), Article No. 41, 2016.
    DOI:10.1145/2925416. (Preprint available at arXiv.org)

  25. Masashi Kiyomi, Yoshio Okamoto, and Yota Otachi,
    On the treewidth of toroidal grids.
    Discrete Applied Mathematics 198 (2016) 303--306.
    DOI:10.1016/j.dam.2015.06.027.

  26. Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno,
    A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares.
    Computational Geometry: Theory and Applications 51 (2016) 25--39.
    DOI:10.1016/j.comgeo.2015.10.004.

  27. Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić, Yoshio Okamoto, Tibor Szabó, and Csaba Tóth,
    Free edge lengths in plane graphs.
    Discrete & Computational Geometry 54 (2015) 259-289.
    DOI:10.1007/s00454-015-9704-z.

  28. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno,
    Swapping Labeled Tokens on Graphs.
    Theoretical Computer Science 586 (2015) 81-94.
    DOI:10.1016/j.tcs.2015.01.052.

  29. Sang Won Bae, Matias Korman, Yoshio Okamoto, and Haitao Wang,
    Computing the L1 geodesic diameter and center of a simple polygon in linear time.
    Computational Geometry: Theory and Applications 48 (2015) 495-505.
    DOI:10.1016/j.comgeo.2015.02.005.
    (Preprint available at arXiv.org)

  30. Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno,
    A 4.31-approximation for the geometric unique coverage problem on unit disks.
    Theoretical Computer Science 544 (2014) 14-31.
    DOI:10.1016/j.tcs.2014.04.014.

  31. Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno,
    Computational complexity and an integer programming model of Shakashaka,
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E97-A (2014) 1213-1219.
    DOI:10.1587/transfun.E97.A.1213.

  32. Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, and Koichi Yamazaki,
    Approximating the path-distance-width for AT-free graphs and graphs in related classes.
    Discrete Applied Mathematics 168 (2014) 69-77.
    DOI:10.1016/j.dam.2012.11.015.

  33. Masayuki Kobayashi and Yoshio Okamoto,
    Submodularity of minimum-cost spanning tree games.
    Networks 63 (2014) 231-238.
    DOI:10.1002/net.21540.
    ( Manuscript: PDF; 135138 bytes)

  34. Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, Hiro Ito, and Yoshio Okamoto,
    The complexity of the stamp folding problem.
    Theoretical Computer Science 497 (2013) 13-19.
    DOI:10.1016/j.tcs.2012.08.006.

  35. Sang Won Bae, Matias Korman, and Yoshio Okamoto,
    The geodesic diameter of polygonal domains.
    Discrete & Computational Geometry 50 (2013) 306-329.
    DOI:10.1007/s00454-013-9527-8.

  36. Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara,
    On bipartite powers of bigraphs.
    Discrete Mathematics & Theoretical Computer Science 14(2) (2012) 11-20.
    Available at http://dmtcs.episciences.org/576.

  37. Hiroshi Toyoizumi, Seiichi Tani, Naoto Miyoshi, and Yoshio Okamoto,
    Reverse preferential spread in complex networks.
    Physical Review E 86, 021103 (2012), 6 pages.
    DOI: 10.1103/PhysRevE.86.021103.

  38. Michael Hoffmann, Jiri Matousek, Yoshio Okamoto, and Philipp Zumstein,
    Minimum and maximum against k lies.
    Chicago Journal of Theoretical Computer Science 2012 (2012), Article 2, pp. 1-10.
    DOI: 10.4086/cjtcs.2012.002 (Open Access).

  39. Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Yoshio Okamoto, and Andreas Spillner,
    Vertex angle and crossing angle resolution of leveled tree drawings.
    Information Processing Letters 112 (2012) 630-635.
    DOI:10.1016/j.ipl.2012.05.006.

  40. Sang Won Bae and Yoshio Okamoto,
    Querying two boundary points for shortest paths in a polygonal domain.
    Computational Geometry: Theory and Applications 45 (2012) 284-293.
    DOI:10.1016/j.comgeo.2012.01.012.
    (Preprint available at arXiv.org)

  41. Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, and Alexander Wolff,
    Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability.
    Algorithmica 62 (2012) 309-332.
    DOI:10.1007/s00453-010-9456-3 (Open Access).

  42. Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno,
    Hardness results and an exact exponential algorithm for the spanning tree congestion problem.
    Journal of Graph Algorithms and Applications 15 (2011) 727-751.
    Available at the JGAA page

  43. Michael Hoffmann, Jiri Matousek, Yoshio Okamoto, Philipp Zumstein,
    The t-pebbling number is eventually linear in t.
    The Electronic Journal of Combinatorics 18(1), P153 (2011), 4 pages.
    Available at the EJC page

  44. Hee-Kap Ahn and Yoshio Okamoto,
    Adaptive algorithms for planar convex hull problems.
    IEICE Transactions on Information and Systems E94-D (2011) 182-189.
    DOI:10.1587/transinf.E94.D.182.
    ( Manuscript: PDF; 195432 bytes)
    © 2011 The Institute of Electronics, Information and Communication Engineers

  45. Yoshio Okamoto and Takeaki Uno,
    A polynomial-time-delay polynomial-space algorithm for enumeration problems in multi-criteria optimization.
    European Journal of Operational Research 210 (2011) 48-56.
    DOI:10.1016/j.ejor.2010.10.008.
    ( Manuscript: PDF; 150563 bytes)
    © 2010 Elsevier B.V.

  46. Yoshinobu Kawahara, Kiyohito Nagano, and Yoshio Okamoto,
    Submodular fractional programming for balanced clustering.
    Pattern Recognition Letters 32 (2011) 235-243.
    DOI:10.1016/j.patrec.2010.08.008.

  47. Ondřej Bílka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin-ichi Tanigawa, and Csaba D. Tóth,
    A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets.
    The Electronic Journal of Combinatorics 17, N35 (2010), 4 pages.
    Available at the EJC page

  48. Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, and Takeaki Uno,
    On listing, sampling, and counting the chordal graphs with edge constraints.
    Theoretical Computer Science 411 (2010) 2591-2601.
    DOI:10.1016/j.tcs.2010.03.024.
    A preliminary version available as RIMS Preprint, RIMS-1610, Kyoto University, 2007.
    ( Preprint: Gzipped Postscript)
    ( Preprint: PDF)

  49. Tobias Christ, Michael Hoffmann, Yoshio Okamoto, and Takeaki Uno,
    Improved bounds for wireless localization.
    Algorithmica 57 (2010) 499-516.
    DOI:10.1007/s00453-009-9287-2.

  50. Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, and Alexander Wolff,
    Untangling a planar graph.
    Discrete & Computational Geometry 42 (2009) 542-569.
    DOI:10.1007/s00454-008-9130-6.
    (Preprint available at arXiv.org)

  51. Komei Fukuda, Sonoko Moriyama, and Yoshio Okamoto,
    The Holt-Klee condition for oriented matroids.
    European Journal of Combinatorics 30 (2009) 1854-1867.
    DOI:10.1016/j.ejc.2008.12.012.
    (Preprint available at arXiv.org)

  52. Heidi Gebauer and Yoshio Okamoto,
    Fast exponential-time algorithms for the forest counting and the Tutte polynomial computation in graph classes.
    International Journal of Foundations of Computer Science 20 (2009) 25-44.
    DOI:10.1142/S0129054109006437.
    ( Manuscript: Gzipped Postscript; 107932 bytes)
    ( Manuscript: PDF; 110880 bytes)
    © World Scientific Publishing Co. 2009.

  53. Yoshio Okamoto,
    Local topology of the free complex of a two-dimensional generalized convex shelling.
    Discrete Mathematics 308 (2008) 3836-3846.
    DOI:10.1016/j.disc.2007.07.078.
    ( Manuscript: Gzipped Postscript; 160621 bytes)
    ( Manuscript: PDF; 126724 bytes)
    © Elsevier B.V. 2008.

  54. Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara,
    Counting the number of independent sets in chordal graphs.
    Journal of Discrete Algorithms 6 (2008) 229-242.
    DOI:10.1016/j.jda.2006.07.006.
    ( Manuscript: Gzipped Postscript; 106368 bytes)
    ( Manuscript: PDF; 108012 bytes)
    © Elsevier B.V. 2008.

  55. Yoshio Okamoto,
    Fair cost allocations under conflicts --- a game-theoretic point of view ---.
    Discrete Optimization 5 (2008) 1-18.
    DOI:10.1016/j.disopt.2007.10.002.
    ( Manuscript: Gzipped Postscript; 199008 bytes)
    ( Manuscript: PDF; 173175 bytes)
    © Elsevier B.V. 2008.

  56. Yota Otachi, Yoshio Okamoto, and Koichi Yamazaki,
    Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs.
    Discrete Applied Mathematics 155 (2007) 2383-2390.
    DOI:10.1016/j.dam.2007.07.010.

  57. Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Uno,
    Matroid representation of clique complexes,
    Discrete Applied Mathematics 155 (2007) 1910-1929.
    DOI:10.1016/j.dam.2007.05.004.
    ( Manuscript: Gzipped Postscript; 145565 bytes)
    ( Manuscript: PDF; 172557 bytes)
    © Elsevier B.V. 2007.

  58. Sonoko Moriyama and Yoshio Okamoto,
    The even outdegree conjecture for acyclic PLCP-cubes in dimension five.
    IEICE Transactions on Information and Systems E89-D (2006) 2402-2404.
    DOI:10.1093/ietisy/e89-d.8.2402.

  59. Thomas Bietenhader and Yoshio Okamoto,
    Core stability of minimum coloring games.
    Mathematics of Operations Research 31 (2006) 418-431.
    DOI:10.1287/moor.1060.0187.
    ( Manuscript: Gzipped Postscript; 155523 bytes)
    ( Manuscript: PDF; 320239 bytes)
    © INFORMS 2006.

  60. Michael Hoffmann and Yoshio Okamoto,
    The minimum weight triangulation problem with few inner points.
    Computational Geometry: Theory and Applications 34 (2006) 149-158.
    DOI:10.1016/j.comgeo.2005.11.006.
    ( Manuscript: Gzipped Postscript; 165328 bytes)
    ( Manuscript: PDF; 178477 bytes)
    © Elsevier B.V. 2006.

  61. Vladimir G. Deineko, Michael Hoffmann, Yoshio Okamoto, and Gerhard J. Woeginger,
    The traveling salesman problem with few inner points,
    Operations Research Letters 34 (2006) 106-110.
    DOI:10.1016/j.orl.2005.01.002.
    ( Manuscript: Gzzipped Postscript; 120491 bytes)
    ( Manuscript: PDF; 119234 bytes)
    © Elsevier B.V. 2006.

  62. Kenji Kashiwabara, Masataka Nakamura, and Yoshio Okamoto,
    The affine representation theorem for abstract convex geometries,
    Computational Geometry: Theory and Applications 30 (2005) 129-144.
    DOI: 10.1016/j.comgeo.2004.05.001.
    ( Manuscript: Gzipped Postscript; 119441 bytes)
    ( Manuscript: PDF; 248564 bytes)
    © Elsevier B.V. 2005.

  63. Yoshio Okamoto,
    Traveling salesman games with the Monge property,
    Discrete Applied Mathematics 138 (2004) 349-369.
    DOI: 10.1016/j.dam.2003.08.005.
    ( Manuscript: Gzipped Postscript; 191811 bytes)
    ( Manuscript: PDF; 208296 bytes)
    © Elsevier B.V. 2004.

  64. Yoshio Okamoto and Masataka Nakamura,
    The forbidden minor characterization of line-search antimatroids of rooted digraphs,
    Discrete Applied Mathematics 131 (2003) 523-533.
    DOI: 10.1016/S0166-218X(02)00471-7.
    ( Manuscript: Gzipped Postscript; 80204 bytes)
    ( Manuscript: PDF; 169961 bytes)
    © Elsevier B.V. 2003.

  65. Kenji Kashiwabara and Yoshio Okamoto,
    A greedy algorithm for convex geometries.
    Discrete Applied Mathematics 131 (2003) 449-465.
    DOI: 10.1016/S0166-218X(02)00467-5.
    ( Manuscript: Gzipped Postscript; 88390 bytes)
    ( Manuscript: PDF; 218744 bytes)
    © Elsevier B.V. 2003.

  66. Yoshio Okamoto,
    Submodularity of some classes of the combinatorial optimization games.
    Mathematical Methods of Operations Research 58 (2003) 131-139.
    DOI: 10.1007/s001860300284.
    ( Manuscript: Gzipped Postscript; 61764 bytes)
    ( Manuscript: PDF; 146436 bytes)
    © Springer-Verlag 2003.

  67. Yoshio Okamoto,
    Some properties of the core on convex geometries.
    Mathematical Methods of Operations Research 56 (2002) 377-386.
    DOI: 10.1007/s001860200218.
    ( Manuscript: Gzipped Postscript; 40672 bytes)
    ( Manuscript: PDF; 125167 bytes)
    © Springer-Verlag 2002.

Refereed Papers in Conferences

  1. Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden,
    Minimum separator reconfiguration.
    Proceedings of 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), to appear.
    (Preprint available at arXiv.org)

  2. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Algorithmic theory of quantum routing.
    Proceedings of 18th Algorithms and Data Structures Symposium (WADS 2023),
    Lecture Notes in Computer Science 14079 (2023) 533--546.
    DOI:10.1007/978-3-031-38906-1_35
    (Preprint available at arXiv.org)

  3. 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.
    Proceedings of 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023),
    Leibniz International Proceedings in Informatics (LIPIcs) 261 (2023) pp. 82:1-82:17.
    DOI:10.4230/LIPIcs.ICALP.2023.82 (Open Access)
    (Preprint available at arXiv.org)

  4. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki,
    Rerouting planar curves and disjoint paths.
    Proceedings of 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023),
    Leibniz International Proceedings in Informatics (LIPIcs) 261 (2023) pp. 81:1-81:19.
    DOI:10.4230/LIPIcs.ICALP.2023.81 (Open Access)
    (Preprint available at arXiv.org)

  5. Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki,
    Reconfiguration of colorings in triangulations of the sphere.
    Proceedings of 39th International Symposium on Computational Geometry (SoCG 2023),
    Leibniz International Proceedings in Informatics (LIPIcs) 258 (2023) pp. 43:1-43:16.
    DOI:10.4230/LIPIcs.SoCG.2023.43 (Open Access)
    (Preprint available at arXiv.org)

  6. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki,
    On reachable assignments under dichotomous preferences.
    Proceedings of 24th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2022),
    Lecture Notes in Computer Science 13753 (2022) 650--658.
    DOI:10.1007/978-3-031-21203-1_43
    Preprint available at arXiv.

  7. Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot,
    Unlabeled multi-robot motion planning with tighter separation bounds.
    Proceedings of 38th International Symposium on Computational Geometry (SoCG 2022),
    Leibniz International Proceedings in Informatics (LIPIcs) 224 (2022) pp. 12:1-12:16.
    DOI:10.4230/LIPIcs.SoCG.2022.12 (Open Access)
    (Preprint available at arXiv.org)

  8. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki,
    Reforming an envy-free matching.
    Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), pp. 5084-5091.
    DOI: 10.1609/aaai.v36i5.20441
    (Preprint available at arXiv.org)

  9. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki,
    Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams.
    Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) pp. 1342-1355.
    DOI: 10.1137/1.9781611977073.56 (Open Access)
    (Preprint available at arXiv.org)

  10. Jakob Geiger, Sabine Cornelsen, Jan-Henrik Haunert, Philipp Kindermann, Tamara Mchedlidze, Martin Nöllenburg, Yoshio Okamoto, and Alexander Wolff,
    ClusterSets: Optimizing planar clusters in categorical point data.
    Proceedings of 23rd EG Conference on Visualization (EuroVis 2021),
    Computer Graphics Forum 40 (2021) 471-481.
    DOI: 10.1111/cgf.14322 (Open Access)

  11. Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Yushi Uno,
    Linear-time recognition of double-threshold graphs.
    Proceedings of 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020),
    Lecture Notes in Computer Science 12301 (2020) 286-297.
    (Preprint available at arXiv.org)

  12. Yoshio Okamoto, Alexander Ravsky, and Alexander Wolff,
    Variants of the segment number of a graph.
    Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019),
    Lecture Notes in Computer Science 11904 (2019) 430-443.
    DOI:10.1007/978-3-030-35802-0_33
    (Preprint available at arXiv.org)

  13. Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Parada, Daniel Perz, André van Renssen, and Birgit Vogtenhuber,
    Graphs with large total angular resolution.
    Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019),
    Lecture Notes in Computer Science 11904 (2019) 193-199.
    DOI:10.1007/978-3-030-35802-0_15
    (Preprint available at arXiv.org)

  14. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Shortest reconfiguration of perfect matchings via alternating cycles .
    Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), 2019,
    Leibniz International Proceedings in Informatics (LIPIcs) 144 (2019) 61:1-61:15.
    DOI:10.4230/LIPIcs.ESA.2019.61 (Open Access)

  15. Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Algorithms for gerrymandering over graphs.
    Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), 2019, pp. 1413-1421.
    Online version freely available

  16. Hans L. Bodlaender, Tesshu Hanaka, Yoshio Okamoto, Yota Otachi, and Tom C. van der Zanden.
    Subgraph isomorphism on graph classes that exclude a substructure.
    Proceedings of 11th International Conference on Algorithms and Complexity (CIAC 2019),
    Lecture Notes in Computer Science 11485 (2019) 87-98.
    DOI:10.1007/978-3-030-17402-6_8

  17. Elena Arseneva, Man-Kwun Chiu, Matias Korman, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen, Marcel Roeloffzen.
    Rectilinear link diameter and radius in a rectilinear polygonal domain.
    Proceedings of 29th International Symposium on Algorithms and Computation (ISAAC 2018),
    Leibniz International Proceedings in Informatics (LIPIcs) 123 (2018) 58:1-58:13.
    DOI:10.4230/LIPIcs.ISAAC.2018.58

  18. Evmorfia Argyriou, Sabine Cornelsen, Henry Förster, Michael Kaufmann, Martin Nöllenburg, Yoshio Okamoto, Chrysanthi Raftopoulou, and Alexander Wolff,
    Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity.
    Proceedings of 26th International Symposium on Graph Drawing and Network Visualization (GD 2018),
    Lecture Notes in Computer Science 11282 (2018) 509-523.
    DOI:10.1007/978-3-030-04414-5_36

  19. Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara,
    Computationa complexity of robot arm simulation problems.
    Proceedings of 29th International Workshop on Combinational Algorithms (IWOCA 2018),
    Lecture Notes in Computer Science 10979 (2018) 177-188.
    DOI:10.1007/978-3-319-94667-2_15

  20. Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa,
    Exact algorithms for the max-min dispersion problem.
    Proceedings of 12th International Frontiers of Algorithmics Workshop (FAW 2018),
    Lecture Notes in Computer Science 10823 (2018) 263-272.
    DOI:10.1007/978-3-319-78455-7_20

  21. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, and Taichi Shiitada.
    Tight approximability of the server allocation problem for real-time applications.
    Proceedings of 3rd International Workshop on Algorithmic Aspects of Cloud Computing (ALGOCLOUD 2017),
    Lecture Notes in Computer Science 10739 (2018) 41-55.
    DOI:10.1007/978-3-319-74875-7_4

  22. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Reconfiguration of maximum-weight b-matchings in a graph.
    Proceedings of 23rd Annual International Computing and Combinatorics Conference (COCOON 2017),
    Lecture Notes in Computer Science 10392 (2017) 287-296.
    DOI:10.1007/978-3-319-62389-4_24

  23. Paz Carmi, Man Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, and Shakhar Smorodinsky,
    Balanced line separators of unit disk graphs.
    Proceedings of 15th Algorithms and Data Structures Symposium (WADS 2017),
    Lecture Notes in Computer Science 10389 (2017) 241-252.
    DOI:10.1007/978-3-319-62127-2_21

  24. Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno,
    Sequentially swapping colored tokens on graphs.
    Proceedings of 11th International Conference and Workshop on Algorithms and Computation (WALCOM 2017),
    Lecture Notes in Computer Science 10167 (2017) 435-447.
    DOI:10.1007/978-3-319-53925-6_34

  25. Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, Takeaki Uno,
    Approximation and hardness of token swapping,
    Proceedings of 24th European Symposium on Algorithms (ESA 2016),
    Leibniz International Proceedings in Informatics (LIPIcs) 57 (2016) 66:1-66:15.
    DOI:10.4230/LIPIcs.ESA.2016.66 (Open Access)

  26. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Efficient stabilization of cooperative matching games.
    Proceedings of 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2016), 2016, pp. 41-49.
    Online version freely available

  27. Sang Won Bae, Matias Korman, Joseph Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang,
    Computing the L1 Geodesic diameter and center of a polygonal domain.
    Proceedings of 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016),
    Leibniz International Proceedings in Informatics (LIPIcs) 47 (2016) 14:1-14:14.
    DOI:10.4230/LIPIcs.STACS.2016.14 (Open Access)

  28. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto,
    Minimum-cost b-edge dominating sets on trees.
    Proceedings of 25th International Symposium on Algorithms and Computation (ISAAC 2014),
    Lecture Notes in Computer Science 8889 (2014) 195-207.
    DOI:10.1007/978-3-319-13075-0_16

  29. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno,
    Swapping labeled tokens on graphs.
    A. Ferro, F. Luccio, and P. Widmayer (eds.),
    Proceedings of 7th International Conference on Fun with Algorithms (FUN 2014),
    Lecture Notes in Computer Science 8496 (2014) 369-380.
    DOI:10.1007/978-3-319-07890-8_31

  30. Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, and Yukiko Yamauchi,
    Sankaku-Tori: An old Western-Japanese game played on a point set.
    A. Ferro, F. Luccio, and P. Widmayer (eds.),
    Proceedings of 7th International Conference on Fun with Algorithms (FUN 2014),
    Lecture Notes in Computer Science 8496 (2014) 235-244.
    DOI:10.1007/978-3-319-07890-8_20

  31. Luis Barba, Otfried Cheong, Jean-Lou De Carufel, Michael Gene Dobbins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot, and Tianhao Wang,
    Weight balancing on boundaries and skeletons.
    Proceedings of 30th Annual Symposium on Computational Geometry (SoCG 2014), 2014, pp. 436-443.
    DOI:10.1145/2582112.2582142

  32. Zachary Abel, Robert Connelly, Sarah Eisenstat, Radoslav Fulek, Filip Morić, Yoshio Okamoto, Tibor Szabó, and Csaba Tóth,
    Free edge lengths in plane graphs.
    Proceedings of 30th Annual Symposium on Computational Geometry (SoCG 2014), 2014, pp. 426-435.
    DOI:10.1145/2582112.2582172

  33. Lukas Barth, Sara Irina Fabrikant, Stephen G. Kobourov, Anna Lubiw, Martin Nöllenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, Torsten Ueckerdt, and Alexander Wolff,
    Semantic word cloud representations: hardness and approximation algorithms.
    Proceedings of 11th Latin American Theoretical Informatics Symposium (LATIN 2014),
    Lecture Notes in Computer Science 8392 (2014) 514-525.
    DOI: 10.1007/978-3-642-54423-1_45

  34. Sang Won Bae, Matias Korman, Yoshio Okamoto, and Haitao Wang,
    Computing the L1 geodesic diameter and center of a simple polygon in linear time .
    Proceedings of 11th Latin American Theoretical Informatics Symposium (LATIN 2014),
    Lecture Notes in Computer Science 8392 (2014) 120-131.
    DOI: 10.1007/978-3-642-54423-1_11

  35. Yoshio Okamoto, Yuichi Tatsu, and Yushi Uno,
    Exact and fixed-parameter algorithms for metro-line crossing minimization problems.
    S. Wismath and A. Wolff (eds.),
    Proceedings of 21st International Symposium on Graph Drawing (GD 2013), Poster Presentation,
    Lecture Notes in Computer Science 8242 (2013) 520-521.

  36. Sang Won Bae, Yoshio Okamoto, and Chan-Su Shin,
    Area bounds of rectilinear polygons realized by angle sequences.
    K.-M. Chao, T.-s. Hsu, and D.-T. Lee (eds.),
    Proceedings of 23rd International Symposium on Algorithms and Computation (ISAAC 2012),
    Lecture Notes in Computer Science 7676 (2012) 629-638.
    DOI: 10.1007/978-3-642-35261-4_65.

  37. Patrizio Angelini, Carla Binucci, William Evans, Ferran Hurtado, Giuseppe Liotta Tamara Mchedlidze, Henk Meijer, and Yoshio Okamoto,
    Universal point subsets for planar graphs.
    K.-M. Chao, T.-s. Hsu, and D.-T. Lee (eds.),
    Proceedings of 23rd International Symposium on Algorithms and Computation (ISAAC 2012),
    Lecture Notes in Computer Science 7676 (2012) 423-432.
    DOI: 10.1007/978-3-642-35261-4_45.

  38. Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno,
    A 4.31-approximation for the geometric unique coverage problem on unit disks.
    K.-M. Chao, T.-s. Hsu, and D.-T. Lee (eds.),
    Proceedings of 23rd International Symposium on Algorithms and Computation (ISAAC 2012),
    Lecture Notes in Computer Science 7676 (2012) 372-381.
    DOI: 10.1007/978-3-642-35261-4_40.

  39. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström,
    On problems as hard as CNF-SAT.
    Proceedings of 27th IEEE Conference on Computational Complexity (CCC 2012), 2012, pp. 74-84.
    DOI: 10.1109/CCC.2012.36.
    (Preprint available at arXiv.org)

  40. Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno,
    A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares.
    F.V. Fomin and P. Kaski (eds.),
    Proceedings of 13th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT 2012),
    Lecture Notes in Computer Science 7357 (2012) 24-35.
    DOI: 10.1007/978-3-642-31155-0_3.

  41. Masashi Kiyomi, Yoshio Okamoto, and Toshiki Saitoh,
    Efficient enumeration of the directed binary perfect phylogenies from incomplete data.
    R. Klasing (ed.),
    Proceedings of 11th International Symposium on Experimental Algorithms (SEA 2012),
    Lecture Notes in Computer Science 7276 (2012) 248-259.
    DOI: 10.1007/978-3-642-30850-5_22.
    (Preprint available at arXiv.org)

  42. Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, and Koichi Yamazaki,
    Approximability of the path-distance-width for AT-free graphs.
    P. Kolman and J. Kratochvil (eds.),
    Proceedings of 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011),
    Lecture Notes in Computer Science 6986 (2011) 271-282.
    DOI: 10.1007/978-3-642-25870-1_25.

  43. Shuji Kijima, Yoshio Okamoto, and Takeaki Uno,
    Dominating set counting in graph classes.
    B. Fu and D.-Z. Du (eds.),
    Proceedings of 17th Annual International Computing and Combinatorics Conference (COCOON 2011),
    Lecture Notes in Computer Science 6842 (2011) 13-24.
    DOI: 10.1007/978-3-642-22685-4_2.
    ( Manuscript: PDF; 102252 bytes)
    © Springer-Verlag 2011.

  44. Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno,
    Hardness results and an exact exponential algorithm for the spanning tree congestion problem.
    M. Ogihara and J. Tarui (eds.),
    Proceedings of 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011),
    Lecture Notes in Computer Science 6648 (2011) 452-462.
    DOI: 10.1007/978-3-642-20877-5_44.
    ( Manuscript: PDF; 68704 bytes)
    © Springer-Verlag 2011.

  45. Sang Won Bae, Matias Korman, and Yoshio Okamoto,
    The geodesic diameter of polygonal domains.
    M. de Berg and U. Meyer (eds.),
    Proceedings of 18th Annual European Symposium on Algorithms (ESA 2010),
    Lecture Notes in Computer Science 6346 (2010) 500-511.
    DOI: 10.1007/978-3-642-15775-2_43.
    (Preprint available at arXiv.org)

  46. Hee-Kap Ahn and Yoshio Okamoto,
    Adaptive algorithms for planar convex hull problems.
    D.T. Lee, D.Z. Chen, and S. Ying (eds.),
    Proceedings of 4th International Frontiers of Algorithmics Workshop (FAW 2010),
    Lecture Notes in Computer Science 6213 (2010) 316-326.
    DOI: 10.1007/978-3-642-14553-7_30.
    ( Manuscript: PDF; 195432 bytes)
    © Springer-Verlag 2010.

  47. Michael Hoffmann, Jiri Matousek, Yoshio Okamoto, and Philipp Zumstein,
    Minimum and maximum against k lies.
    H. Kaplan (ed.),
    Proceedings of 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010),
    Lecture Notes in Computer Science 6139 (2010) 139-149.
    DOI: 10.1007/978-3-642-13731-0_14.
    (Preprint available at arXiv.org)

  48. Yoshio Okamoto, Ryuhei Uehara, and Takeaki Uno,
    Counting the number of matchings in chordal and chordal bipartite graph classes.
    C. Paul and M. Habib (eds.),
    Proceedings of 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009),
    Lecture Notes in Computer Science 5911 (2010) 296-307.
    DOI: 10.1007/978-3-642-11409-0_26.
    ( Manuscript: PDF; 184054 bytes)
    © Springer-Verlag 2010.

  49. Sang Won Bae and Yoshio Okamoto,
    Querying two boundary points for shortest paths in a polygonal domain.
    Y. Dong, D.-Z. Du, and O. Ibarra (eds.),
    Proceedings of 20th International Symposium on Algorithms and Computation (ISAAC 2009),
    Lecture Notes in Computer Science 5878 (2009) 1054-1063.
    DOI: 10.1007/978-3-642-10631-6_106.
    (Preprint available at arXiv.org)

  50. Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, and Alexander Wolff,
    Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability.
    I.G. Tollis and M. Patrignani (eds.),
    Proceedings of 16th International Symposium on Graph Drawing (GD 2008),
    Lecture Notes in Computer Science 5417 (2009) 324-335.
    DOI: 10.1007/978-3-642-00219-9_32.
    (Preprint available at arXiv.org)

  51. Tobias Christ, Michael Hoffmann, Yoshio Okamoto, and Takeaki Uno,
    Improved bounds for wireless localization.
    J. Gudmundsson (ed.),
    Proceedings of 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008),
    Lecture Notes in Computer Science 5124 (2008) 77-89 .
    DOI: 10.1007/978-3-540-69903-3_9.
    ( Manuscript: PDF; 296450 bytes)
    © Springer-Verlag 2008.

  52. Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, and Takeaki Uno,
    On listing, sampling, and counting the chordal graphs with edge constraints.
    X. Hu and J. Wang (eds.),
    Proceedings of 14th Annual International Computing and Combinatorics Conference (COCOON 2008),
    Lecture Notes in Computer Science 5092 (2008) 458-467.
    DOI: 10.1007/978-3-540-69733-6_45.
    Preliminary version available as RIMS Preprint, RIMS-1610, Kyoto University, 2007.
    ( Preprint: Gzipped Postscript)
    ( Preprint: PDF)

  53. Xavier Goaoc, Jan Kratochvil, Yoshio Okamoto, Chan-Su Shin, and Alexander Wolff,
    Moving vertices to make drawings plane.
    S.-H. Hong, T. Nishizeki, and W. Quan (eds.),
    Proceedings of 15th International Symposium on Graph Drawing (GD 2007),
    Lecture Notes in Computer Science 4875 (2008) 101-112.
    DOI: 10.1007/978-3-540-77537-9_13.
    (Preprint available at arXiv.org)

  54. Yoshio Okamoto and Takeaki Uno,
    A polynomial-time-delay polynomial-space algorithm for enumeration problems in multi-criteria optimization.
    T. Tokuyama (ed.),
    Proceedings of 18th International Symposium on Algorithms and Computation (ISAAC 2007),
    Lecture Notes in Computer Science 4835 (2007) 609-620.
    DOI: 10.1007/978-3-540-77120-3_53.
    ( Manuscript: Gzipped Postscript; 146217 bytes)
    ( Manuscript: PDF; 112161 bytes)
    © Springer-Verlag 2007.

  55. Heidi Gebauer and Yoshio Okamoto,
    Fast exponential-time algorithms for the forest counting in graph classes.
    J. Gudmundsson and B. Jay (eds.),
    Proceedings of 13th Computing: The Australasian Theory Symposium (CATS 2007),
    Conferences in Research and Practice in Information Technology 65 (2007) 63-69.
    ( Manuscript: Gzipped Postscript; 140395 bytes)
    ( Manuscript: PDF; 165165 bytes)
    © Australian Computer Soceity, Inc. 2007.

  56. Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara,
    Linear-time counting algorithms for independent sets in chordal graphs.
    D. Kratsch (ed.),
    Proceedings of 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005),
    Lecture Notes in Computer Science 3787 (2005) 433-444.
    DOI: 10.1007/11604686_38.

  57. Thomas Bietenhader and Yoshio Okamoto,
    Core stability of minimum coloring games,
    J. Hromkovic, M. Nagl, B. Westfechtel (eds.),
    Proceedings of 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004),
    Lecture Notes in Computer Science 3353 (2004) 389-401.
    DOI: 10.1007/978-3-540-30559-0_33
    ( Manuscript: Gzipped Postscript; 78730 bytes)
    ( Manuscript: PDF; 161961 bytes)
    © Springer-Verlag 2004.

  58. Michael Hoffmann and Yoshio Okamoto,
    The minimum weight triangulation problem with few inner points.
    R. Downey, M. Fellows, F. Dehne (eds.),
    Proceedings of 1st International Workshop on Parameterized and Exact Computation (IWPEC 2004),
    Lecture Notes in Computer Science 3162 (2004) 200-212.
    DOI: 10.1007/978-3-540-28639-4_18
    ( Manuscript: Gzipped Postscript; 74253 bytes)
    ( Manuscript: PDF; 205657 bytes)
    © Springer-Verlag 2004.

  59. Vladimir G. Deineko, Michael Hoffmann, Yoshio Okamoto, and Gerhard J. Woeginger,
    The traveling salesman problem with few inner points (extended abstract version),
    K.-Y. Chwa and J. I. Munro (eds.),
    Proceedings of 10th International Computing and Combinatorics Conference (COCOON 2004),
    Lecture Notes in Computer Science 3106 (2004) 268-277.
    DOI: 10.1007/978-3-540-27798-9_30
    ( Manuscript: Gzipped Postscript; 76090 bytes)
    ( Manuscript: PDF; 154502 bytes)
    © Springer-Verlag 2004.

  60. Yoshio Okamoto,
    Fair cost allocations under conflicts --- a game-theoretic point of view --- (extended abstract version).
    T. Ibaraki, N. Katoh and H. Ono (eds.),
    Proceedings of 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003),
    Lecture Notes in Computer Science 2906 (2003) 686-695.
    DOI: 10.1007/978-3-540-24587-2_70
    ( Manuscript: Gzipped Postscript; 128235 bytes)
    ( Manuscript: PDF; 163851 bytes)
    © Springer-Verlag 2003.

  61. Paz Carmi, Thomas Erlebach, and Yoshio Okamoto,
    Greedy edge-disjoint paths in complete graphs (extended abstract version).
    H.L. Bodlaender (ed.),
    Proceedings of 29th Workshop on Graph Theoretic Concepts in Computer Science (WG 2003),
    Lecture Notes in Computer Science 2880 (2003) 143-155.
    DOI: 10.1007/978-3-540-39890-5_13
    ( Manuscript: Gzipped Postscript; 162501 bytes)
    ( Manuscript: PDF; 157159 bytes)
    © Springer-Verlag 2003.

  62. Yoshio Okamoto,
    The free complex of a two-dimensional generalized convex shelling (abstract version for Eurocomb'03).
    J. Fiala (ed.),
    EUROCOMB'03 -- Abstracts, ITI Series 2003-145, Institute for Theoretical Computer Science (ITI), Charles University, 2003, pp. 289-293.
    ( Manuscript: Gzipped Postscript; 41435 bytes)
    ( Manuscript: PDF; 113371 bytes)

  63. Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Uno,
    Matroid representation of clique complexes (extended abstract version).
    T. Warnow and B. Zhu (eds.),
    Proceedings of 9th International Computing and Combinatorics Conference (COCOON 2003),
    Lecture Notes in Computer Science 2697 (2003) 192-201.
    DOI: 10.1007/3-540-45071-8_21
    ( Manuscript: Gzipped Postscript; 45654 bytes)
    ( Manuscript: PDF; 131631 bytes)
    © Springer-Verlag 2003.

Software

  1. Katsuki Fujisawa, Sunyoung Kim, Masakazu Kojima, Yoshio Okamoto, and Makoto Yamashita,
    SparseCoLo: Conversion Methods for SPARSE COnic-form Linear Optimization,
    Available from M. Kojima's page.

    Associated Techinical Report:
    User's Manual forSparseCoLO: Conversion Methods for SPARSE COnic-form Linear Optimization Problems
    Department of Mathematical and Computer Sciences Research Report, B-453, 2009.
    Available here

Preprints

  1. Heidi Gebauer, Anna Gundert, Robin A. Moser, and Yoshio Okamoto,
    Not all saturated 3-forests are tight.
    arXiv:1109.3390, 2011.

  2. Yusuke Kuroki, Yoshio Okamoto, and Kazuya Shirahata,
    Analysis of quicksort in terms of inversions.
    Preprint, 2010.

Edited Volumes

  1. Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, and Osamu Watanabe (eds.),
    Proceedings of 22nd International Symposium on Algorithms and Computation (ISAAC 2011),
    Lecture Notes in Computer Science 7074, Springer 2011.
    DOI: 10.1007/978-3-642-25591-5.

Contributions in Books

  1. Yoshio Okamoto,
    Traveling sales person with few inner points.
    Ming-Yang Kao (ed.),
    Encyclopedia of Algorithms, Springer, 2008, pp. 961-964.
    DOI: 10.1007/978-0-387-30162-4_426.

Translation of books

  1. Matthias Beck and Sinai Robins,
    Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra.
    Japanese Translation by Yoshio Okamoto, Springer Japan, 2010.
    (Information provided by Springer Japan)

  2. Jiri Matousek,
    Lectures on Discrete Geometry.
    Japanese Translation by Yoshio Okamoto,
    Springer-Verlag Tokyo, 2005.
    ( Information provided by myself in Japanese)

  3. Günter M. Ziegler,
    Lectures on Polytopes.
    Japanese Translation by Masahiro Hachimori and Yoshio Okamoto,
    Springer-Verlag Tokyo, 2003.
    ( Information provided by Masahiro Hachimori in Japanese)
    ( Information provided by Springer-Verlag Tokyo in Japanese)

Thesis

  1. Yoshio Okamoto,
    Structural Parameters in Combinatorial Objects.
    PhD Thesis, Department of Computer Science, ETH Zurich,
    Dissertation Number 15901.
    ( Manuscript: Gzipped Postscript; 366278 bytes)
    ( Manuscript: PDF; 854178 bytes)
    DOI: 10.3929/ethz-a-004931505

  2. Yoshio Okamoto,
    Several Aspects of Antimatroids and Convex Geometries.
    Master's Thesis, Department of Systems Science, Graduate School of Arts and Sciences, The University of Tokyo, 2001.
    ( Manuscript: Gzipped Postscript; 233302 bytes)

Other Reports, Abstracts

(restricted to articles in English)
  1. Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno,
    Computational complexity and an integer programming model of Shakashaka,
    25th Canadian Conference on Computational Geometry (CCCG 2013).

  2. Sang Won Bae, Matias Korman, Yoshio Okamoto, and Haitao Wang,
    Computing the L1 Geodesic Diameter and Center of a Simple Polygon in Linear Time.
    The 16th Korea-Japan Joint Workshop on Algorithms and Computation, 2013.

  3. Luis Barba, Jean-Lou De Carufel, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, Yuan Tang, Takeshi Tokuyama, and Sander Verdonschot, Tianhao Wang,
    Geometric Weight Balancing.
    The 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC), 1 page.

  4. Sang Won Bae, Yoshio Okamoto, and Chan-Su Shin,
    Area bounds of rectilinear polygons realized by angle sequences.
    15th Japan-Korea Joint Workshop on Algorihtms and Computation

  5. Yoshio Okamoto and Stefan Langerman,
    Planar convex hulls against lies.
    4th AAAC meeting, 1 page.

  6. Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara,
    Bipartite powers of interval bigraphs.
    China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), 2 pages.

  7. Hee-Kap Ahn, Yoshio Okamoto, Iris Reinbacher,
    Tracing a virus.
    3rd AAAC meeting, 1 page.

  8. Sang Won Bae, Matias Korman, and Yoshio Okamoto,
    On the geodesic diameter in polygonal domains.
    Abstracts of Japan Conference on Computational Geometry and Graphs (JCCGG 2009), 2 pages.

  9. Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin-ichi Tanigawa, and Csaba D. Tóth,
    A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets.
    Abstracts of Japan Conference on Computational Geometry and Graphs (JCCGG 2009), 2 pages.

  10. Yoshio Okamoto, and Ryuhei Uehara,
    How to make a picturesque maze.
    Proceedings of 21st Canadian Conference on Computational Geometry (CCCG 2009), 137-140.
    ( Manuscript: PDF; 854178 bytes)
    Update is available here.

  11. Tobias Christ, Michael Hoffmann, and Yoshio Okamoto,
    Natural wireless localization is NP-hard.
    Abstracts of 25th European Workshop on Computational Geometry, 2009, 175-178.

  12. Hee-Kap Ahn and Yoshio Okamoto,
    Adaptive computational geometry.
    Proceedings of RIMS Workshop on Computational Geometry and Discrete Mathematics, 2008, pp. 51-54.

  13. Yusuke Abe and Yoshio Okamoto,
    Algorithmic enumeration of higher-order Delaunay triangulations.
    Proceedings of 11th Japan-Korea Joint Workshop on Algorithms and Computation, 2008.
    ( Manuscript: PDF; 139375 bytes)

  14. Masayuki Kobayashi and Yoshio Okamoto,
    Submodularity of minimum-cost spanning tree games.
    Proceedings of 1st ACCC Annual Meeting, 2008, p. 38.

  15. Yoshio Okamoto and Takeaki Uno,
    A provably efficient algorithm for the multi-criteria linear programming.
    Proceedings of 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2007, pp. 87-96.

  16. Takehiro Ito, Yoshio Okamoto, and Takeshi Tokuyama,
    Algorithms for the full Steiner tree problem.
    Proceedings of ICALP'06 Affiliated Workshop "Improving Exponential Time Algorithms," 2006, pp. 39-45.

  17. Heidi Gebauer and Yoshio Okamoto,
    Fast exponential-time algorithms for the forest counting in graph classes.
    Proceedings of ICALP'06 Affiliated Workshop "Improving Exponential Time Algorithms," 2006, pp. 25-30.

  18. Hiroki Nakayama, Sonoko Moriyama, Komei Fukuda, and Yoshio Okamoto,
    Comparing the strengths of the non-realizability certificates for oriented matroids.
    Proceedings of 4th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, 2005, pp. 243-249.

  19. Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara,
    Counting the independent sets of a chordal graph in linear time.
    Proceedings of 4th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, 2005, pp. 257-263.

  20. Kenji Kashiwabara, Masataka Nakamura, and Yoshio Okamoto,
    Affine representations of abstract convex geometries (extended abstract version).
    Abstracts of 19th European Workshop on Computational Geometry, 2003, 77-80.
    ( Manuscript: Gzipped Postscript; 33420 bytes)

  21. Paz Carmi, Thomas Erlebach, and Yoshio Okamoto,
    Greedy edge-disjoint paths in complete graphs (technical report version).
    TIK-Report 155, Computer Engineering and Networks Laboratory (TIK), ETH Zürich, 2002.
    ( Manuscript: PDF; 149507 bytes)
    ( Manuscript: Gzipped Postscript; 121200 bytes)

  22. Kenji Kashiwabara Yoshio Okamoto and Takeaki Uno,
    Matroid representation of clique complexes (preliminary version).
    Proceedings of the 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2003, pp. 40-48.
    ( Manuscript: Gzipped Postscript; 48927 bytes)

  23. Yoshio Okamoto,
    Traveling salesman games with the Monge property (extended abstract version).
    ICM2002GTA Proceeding Volume, 2002, pp. 625-629.

  24. Yoshio Okamoto,
    Core stability of games on convex geometries (preliminary version).
    Summaries of the 2nd International Conference on Nonlinear Analysis and Convex Analysis, 2001, (CD-ROM).
    ( Manuscript: Gzipped Postscript; 62779 bytes)

  25. Yoshio Okamoto,
    Core stability of games on convex geometries (abstract).
    Abstracts of the 2nd International Conference on Nonlinear Analysis and Convex Analysis, 2001, p. 128.
    ( Manuscript: Gzipped Postscript; 37286 bytes)

  26. Yoshio Okamoto,
    Traveling salesman games with the Monge property (preliminary version).
    Proceedings of the 6th Korea-Japan Workshop on Algorithms and Computation, 2001, pp. 75-82.
    ( Manuscript: Gzipped Postscript; 81874 bytes)

  27. Yoshio Okamoto,
    Circuits of antimatroids and Dilworth's decomposition theorem.
    Information and Communication Studies, Vol. 25, Faculty of Information and Communications, Bunkyo University, 2000, pp. 43-54.

  28. Yoshio Okamoto and Masataka Nakamura,
    Forbidden minors for point-search antimatroids and line-search antimatroids of rooted graphs (abstract version).
    Abstracts of Japan Conference on Discrete and Computational Geometry 2000, pp. 91-92.
    ( Manuscript: Gzipped Postscript; 48206 bytes)

  29. Yoshio Okamoto and Kenji Kashiwabara,
    A greedy algorithm for convex geometries (extended abstract version).
    Proceedings of the 5th Japan-Korea Joint Workshop on Algorithms and Computation, 2000, pp. 118-121.
    ( Manuscript: Gzipped Postscript; 58478 bytes)

[Top]
okamotoy@uec.ac.jp