2024/04/22 更新

写真a

オオタチ ヨウタ
大舘 陽太
OTACHI Yota
所属
大学院情報学研究科 数理情報学専攻 数理情報モデル論 准教授
大学院担当
大学院情報学研究科
学部担当
情報学部 自然情報学科
職名
准教授
外部リンク

学位 1

  1. 博士(工学) ( 2010年3月   群馬大学 ) 

研究キーワード 2

  1. グラフアルゴリズム

  2. アルゴリズム

研究分野 2

  1. 情報通信 / 数理情報学

  2. 情報通信 / 情報学基礎論

経歴 4

  1. 名古屋大学   大学院情報学研究科 数理情報学専攻   准教授

    2020年3月 - 現在

      詳細を見る

    国名:日本国

    researchmap

  2. 熊本大学   大学院先端科学研究部   准教授

    2017年5月 - 2020年2月

      詳細を見る

  3. 北陸先端科学技術大学院大学   情報科学研究科   助教

    2012年4月 - 2017年4月

      詳細を見る

  4. 東北大学   大学院情報科学研究科   助教

    2011年4月 - 2012年3月

      詳細を見る

学歴 3

  1. 群馬大学   工学研究科

    - 2010年3月

      詳細を見る

    国名: 日本国

  2. 群馬大学   工学研究科

    - 2007年3月

      詳細を見る

    国名: 日本国

  3. 群馬大学   工学部

    - 2005年3月

      詳細を見る

    国名: 日本国

受賞 7

  1. The best paper award

    2024年3月   WALCOM 2024   Structural parameterizations of vertex integrity

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi

     詳細を見る

    受賞区分:国際学会・会議・シンポジウム等の賞 

  2. 研究会優秀賞

    2021年6月   人工知能学会   多様な部分グラフを発見するアルゴリズム

    土中 哲秀, 小林 靖明, 栗田 和宏, 大舘 陽太

     詳細を見る

  3. 山下記念研究賞

    2019年3月   情報処理学会  

     詳細を見る

    受賞区分:国内学会・会議・シンポジウム等の賞  受賞国:日本国

  4. LA/EATCS-Japan発表論文賞

    2018年2月   LAシンポジウム/EATCS Japan Chapter  

     詳細を見る

    受賞区分:国内学会・会議・シンポジウム等の賞  受賞国:日本国

  5. LA/EATCS-Japan発表論文賞

    2017年2月   LAシンポジウム/EATCS Japan Chapter  

     詳細を見る

    受賞区分:国内学会・会議・シンポジウム等の賞  受賞国:日本国

  6. 北陸先端科学技術大学院大学 学長賞(研究活動賞)

    2015年10月   北陸先端科学技術大学院大学  

     詳細を見る

    受賞国:日本国

  7. コンピュータサイエンス領域奨励賞

    2011年9月   情報処理学会  

     詳細を見る

    受賞区分:国内学会・会議・シンポジウム等の賞  受賞国:日本国

▼全件表示

 

論文 141

  1. Computational complexity of jumping block puzzles. 査読有り

    Masaaki Kanzaki, Yota Otachi, Giovanni Viglietta, Ryuhei Uehara

    Theor. Comput. Sci.   983 巻   頁: 114292 - 114292   2024年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2023.114292

    researchmap

  2. Extended MSO Model Checking via Small Vertex Integrity. 査読有り

    Tatsuya Gima, Yota Otachi

    Algorithmica   86 巻 ( 1 ) 頁: 147 - 170   2024年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-023-01161-9

    researchmap

  3. Dichotomies for Tree Minor Containment with Structural Parameters 査読有り

    Tatsuya Gima, Soh Kumabe, Kazuhiro Kurita, Yuto Okada, Yota Otachi

        2024年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/978-981-97-0566-5_28

    researchmap

  4. Structural Parameterizations of Vertex Integrity 査読有り

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi

        2024年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/978-981-97-0566-5_29

    researchmap

  5. Orientable Burning Number of Graphs 査読有り

    Julien Courtiel, Paul Dorbec, Tatsuya Gima, Romain Lecoq, Yota Otachi

        2024年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/978-981-97-0566-5_27

    researchmap

  6. On the Complexity of List H-Packing for Sparse Graph Classes 査読有り

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou

        2024年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/978-981-97-0566-5_30

    researchmap

  7. Sorting balls and water: Equivalence and computational complexity. 査読有り

    Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

    Theor. Comput. Sci.   978 巻   頁: 114158 - 114158   2023年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2023.114158

    researchmap

  8. Reconfiguration of cliques in a graph. 査読有り

    Takehiro Ito, Hirotaka Ono, Yota Otachi

    Discret. Appl. Math.   333 巻   頁: 43 - 58   2023年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.dam.2023.01.026

    researchmap

  9. A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems. 査読有り

    Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi

    AAAI     頁: 3968 - 3976   2023年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    researchmap

    その他リンク: https://dblp.uni-trier.de/rec/conf/aaai/2023

  10. Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond. 査読有り

    Tesshu Hanaka, Hirotaka Ono, Yota Otachi, Saeki Uda

    Algorithms and Complexity - 13th International Conference(CIAC)     頁: 263 - 277   2023年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-031-30448-4_19

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/ciac/ciac2023.html#HanakaOOU23

  11. Sequentially Swapping Tokens: Further on Graph Classes. 査読有り

    Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

    SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science(SOFSEM)     頁: 222 - 235   2023年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-031-23101-8_15

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/sofsem/sofsem2023.html#KiyaOOO23

  12. Reconfiguring (non-spanning) arborescences 査読有り 国際誌

    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

    Theoretical Computer Science     2022年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Elsevier BV  

    DOI: 10.1016/j.tcs.2022.12.007

    researchmap

  13. Grundy Distinguishes Treewidth from Pathwidth. 査読有り

    Rémy Belmonte, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Yota Otachi

    SIAM Journal on Discrete Mathematics   36 巻 ( 3 ) 頁: 1761 - 1787   2022年9月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1137/20m1385779

    researchmap

  14. Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited. 査読有り

    Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi

    ESA     頁: 61 - 15   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.ESA.2022.61

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/esa/esa2022.html#GimaIKO22

  15. Sorting Balls and Water: Equivalence and Computational Complexity. 査読有り

    Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

    FUN     頁: 16 - 17   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.FUN.2022.16

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/fun/fun2022.html#ItoKMOSSUUYY22

  16. Reconfiguration of Regular Induced Subgraphs. 査読有り

    Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa

    WALCOM     頁: 35 - 46   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.1007/978-3-030-96731-4_4

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/walcom/walcom2022.html#EtoIKOW22

  17. Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets. 査読有り

    Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, Saket Saurabh

    MFCS     頁: 6 - 15   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.MFCS.2022.6

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2022.html#AbhinavBBKNOS22

  18. Parameterized Complexity of Graph Burning. 査読有り

    Yasuaki Kobayashi, Yota Otachi

    Algorithmica   84 巻 ( 8 ) 頁: 2379 - 2393   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-022-00962-8

    researchmap

  19. Parameterized Complexity of (A, ℓ )-Path Packing. 査読有り

    Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

    Algorithmica   84 巻 ( 4 ) 頁: 871 - 895   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-021-00875-y

    researchmap

  20. Independent Set Reconfiguration on Directed Graphs. 査読有り

    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa

    MFCS     頁: 58 - 15   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.MFCS.2022.58

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/mfcs/mfcs2022.html#ItoIKNOTW22

  21. Exploring the gap between treedepth and vertex cover through vertex integrity. 査読有り

    Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

    Theor. Comput. Sci.   918 巻   頁: 60 - 76   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2022.03.021

    researchmap

  22. Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study. 査読有り

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi

    AAAI     頁: 3758 - 3766   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    researchmap

    その他リンク: https://dblp.uni-trier.de/rec/conf/aaai/2022

  23. An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion. 査読有り

    Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi

    Theory Comput. Syst.   66 巻 ( 2 ) 頁: 502 - 515   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00224-022-10076-x

    researchmap

  24. Extended MSO Model Checking via Small Vertex Integrity. 査読有り

    Tatsuya Gima, Yota Otachi

    33rd International Symposium on Algorithms and Computation(ISAAC)     頁: 20 - 15   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

    DOI: 10.4230/LIPIcs.ISAAC.2022.20

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/isaac/isaac2022.html#GimaO22

  25. Linear-Time Recognition of Double-Threshold Graphs. 査読有り

    Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

    Algorithmica   84 巻 ( 4 ) 頁: 1163 - 1181   2022年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-021-00921-9

    researchmap

  26. Finding diverse trees, paths, and more 査読有り

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi

    AAAI 2021: Proceedings of the 35th AAAI Conference on Artificial Intelligence     2021年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

  27. Token Sliding on Split Graphs. 査読有り

    Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora

    Theory of Computing Systems   65 巻 ( 4 ) 頁: 662 - 686   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00224-020-09967-8

    researchmap

  28. Reconfiguring Directed Trees in a Digraph. 査読有り

    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

    Computing and Combinatorics - 27th International Conference(COCOON)     頁: 343 - 354   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-89543-3_29

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/cocoon/cocoon2021.html#ItoIKNOW21

  29. On the security number of the Cartesian product of graphs. 査読有り

    Marko Jakovac, Yota Otachi

    Discrete Applied Mathematics   304 巻   頁: 119 - 128   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.dam.2021.07.030

    researchmap

  30. Low-congestion shortcut and graph parameters. 査読有り

    Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

    Distributed Computing   34 巻 ( 5 ) 頁: 349 - 365   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00446-021-00401-x

    researchmap

  31. Longest common subsequence in sublinear space. 査読有り

    Masashi Kiyomi, Takashi Horiyama, Yota Otachi

    Information Processing Letters   168 巻   頁: 106084 - 106084   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.ipl.2020.106084

    researchmap

  32. Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity. 査読有り

    Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

    Algorithms and Complexity - 12th International Conference(CIAC)     頁: 271 - 285   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-75242-2_19

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/ciac/ciac2021.html#GimaHKKO21

  33. Distributed Reconfiguration of Spanning Trees. 査読有り

    Yukiko Yamauchi, Naoyuki Kamiyama, Yota Otachi

    Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium(SSS)     頁: 516 - 520   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-91081-5_40

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/sss/sss2021.html#YamauchiKO21

  34. Computational Complexity of Jumping Block Puzzles. 査読有り

    Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara

    Computing and Combinatorics - 27th International Conference(COCOON)     頁: 655 - 667   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-89543-3_54

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/cocoon/cocoon2021.html#KanzakiOU21

  35. Parameterized complexity of graph burning 査読有り

    Yasuaki Kobayashi, Yota Otachi

    Leibniz International Proceedings in Informatics   180 巻   頁: 21:1-21:10   2020年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.IPEC.2020.21

  36. Subgraph isomorphism on graph classes that exclude a substructure 査読有り 国際共著

    Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Tom van der Zanden

    Algorithmica   82 巻   頁: 3566-3587   2020年12月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-020-00737-z

  37. Linear-time recognition of double-threshold graphs 査読有り

    Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

    Lecture Notes in Computer Science   12301 巻   頁: 286-297   2020年10月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.1007/978-3-030-60440-0_23

  38. Symmetric assembly puzzles are hard, beyond a few pieces 査読有り 国際共著

    Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S.B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, Yushi Uno

    Computational Geometry: Theory and Applications   90 巻   頁: Article 101648   2020年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.comgeo.2020.101648

  39. Independent set reconfiguration parameterized by modular-width 査読有り 国際共著

    Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

    Algorithmica   82 巻   頁: 2586-2605   2020年9月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-020-00700-y

  40. Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs 査読有り

    Taisuke Izumi, Yota Otachi

    Leibniz International Proceedings in Informatics   168 巻   頁: 67:1-67:17   2020年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.ICALP.2020.67

  41. Parameterized Orientable Deletion 査読有り 国際共著

    Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

    Algorithmica   82 巻   頁: 1909-1938   2020年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-020-00679-6

  42. Parameterized Complexity of $$(A,\ell )$$-Path Packing 査読有り 国際共著

    Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

    Lecture Notes in Computer Science   12126 巻   頁: 43 - 55   2020年6月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:論文集(書籍)内論文   出版者・発行元:Springer International Publishing  

    DOI: 10.1007/978-3-030-48966-3_4

    researchmap

  43. Hedonic seat arrangement problems (Extended abstract) 査読有り 国際共著

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

    AAMAS 2020: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems     頁: 1777-1779   2020年5月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

  44. Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph 査読有り 国際共著

    Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa

    Theoretical Computer Science   818 巻   頁: 2-11   2020年5月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2018.08.009

  45. Space-efficient algorithms for longest increasing subsequence 査読有り 国際共著

    Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

    Theory of Computing Systems   64 巻   頁: 522-541   2020年4月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00224-018-09908-6

  46. Parameterized complexity of safe set 査読有り 国際共著

    Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

    Journal of Graph Algorithms and Applications   24 巻   頁: 215-245   2020年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.7155/jgaa.00528

  47. Grundy Distinguishes Treewidth from Pathwidth. 査読有り 国際共著

    Rémy Belmonte, Eun Jung Kim 0002, Michael Lampis, Valia Mitsou, Yota Otachi

    28th Annual European Symposium on Algorithms(ESA)   173 巻   頁: 14 - 19   2020年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

    DOI: 10.4230/LIPIcs.ESA.2020.14

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/esa/esa2020.html#Belmonte0LMO20

  48. K3 Edge Cover Problem in a Wide Sense. 査読有り 国際共著

    Kyohei Chiba, Rémy Belmonte, Hiro Ito, Michael Lampis, Atsuki Nagao, Yota Otachi

    Journal of Information Processing   28 巻 ( 0 ) 頁: 849 - 858   2020年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.2197/ipsjjip.28.849

    researchmap

  49. Hedonic Seat Arrangement Problems. 査読有り

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

    Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems(AAMAS)     頁: 1777 - 1779   2020年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:International Foundation for Autonomous Agents and Multiagent Systems  

    researchmap

    その他リンク: https://dblp.uni-trier.de/conf/atal/2020

  50. A Survey on Spanning Tree Congestion.

    Yota Otachi

    Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday     頁: 165 - 172   2020年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-42071-0_12

    researchmap

    その他リンク: https://dblp.uni-trier.de/db/conf/birthday/bodlaender2020.html#Otachi20

  51. Combined graph kernels for automatic patent classification: A hybrid approach 査読有り

    Budi Nugroho, Masayoshi Aritsugi, Yota Otachi, Yuki Manabe

    World Patent Information   57 巻   頁: 18 - 24   2019年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    © 2019 Elsevier Ltd In this study, we proposed combined kernel-based methods to leverage patent citation graph performance for patent classification. The concept is to use the combined graph kernels of the citation graph to classify patent documents, as a hybrid approach. A multiple kernel framework was used for integrating multiple datasets of various kernels into a combined kernel. We employed seven graph kernels as the baselines and the combination of random walks and Weisfeiler–Lehman subtree kernels to achieve higher performance. We calculated the kernel values of each patent pairwise and employed an SVM classifier to carry out the classification task. The investigation results demonstrate that the combined graph kernel outperforms single kernels.

    DOI: 10.1016/j.wpi.2019.03.002

    Scopus

    researchmap

  52. Subgraph Isomorphism on Graph Classes that Exclude a Substructure. 査読有り 国際共著

    Hans L. Bodlaender, Tesshu Hanaka, Yoshio Okamoto, Yota Otachi, Tom C. van, der Zanden

    Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings   11485 巻   頁: 87 - 98   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-17402-6_8

    researchmap

  53. Independent Set Reconfiguration Parameterized by Modular-Width. 査読有り 国際共著

    Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

    Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers   11789 巻   頁: 285 - 297   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-30786-8_22

    researchmap

  54. Low-Congestion Shortcut and Graph Parameters. 査読有り

    Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

    Leibniz International Proceedings in Informatics   146 巻   頁: 25:1-25:17   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.DISC.2019.25

  55. Parameterized Complexity of Safe Set. 査読有り 国際共著

    Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

    Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings   11485 巻   頁: 38 - 49   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-030-17402-6_4

    researchmap

  56. How Bad is the Freedom to Flood-It? 査読有り 国際共著

    Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

    J. Graph Algorithms Appl.   23 巻 ( 2 ) 頁: 111 - 134   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.7155/jgaa.00486

    researchmap

  57. A lower bound on opaque sets. 査読有り 国際共著

    Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, János Pach

    Comput. Geom.   80 巻   頁: 13 - 22   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.comgeo.2019.01.002

    researchmap

  58. On the Classes of Interval Graphs of Limited Nesting and Count of Lengths. 査読有り 国際共著

    Pavel Klavík, Yota Otachi, Jirí Sejnoha

    Algorithmica   81 巻 ( 4 ) 頁: 1490 - 1511   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1007/s00453-018-0481-y

    Scopus

    researchmap

  59. On structural parameterizations of firefighting. 査読有り 国際共著

    Bireswar Das, Murali Krishna Enduri, Masashi Kiyomi, Neeldhara Misra, Yota Otachi, I. Vinod Reddy, Shunya Yoshimura

    Theor. Comput. Sci.   782 巻   頁: 79 - 90   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2019.02.032

    researchmap

  60. On Computational Complexity of Pipe Puzzles 査読有り

    SHIRAYAMA Takumu, SHIGEMURA Takuto, OTACHI Yota, MIYAZAKI Shuichi, UEHARA Ryuhei

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   102 巻 ( 9 ) 頁: 1134 - 1141   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人 電子情報通信学会  

    <p>In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.</p>

    DOI: 10.1587/transfun.E102.A.1134

  61. Reconfiguration of colorable sets in classes of perfect graphs. 査読有り

    Takehiro Ito, Yota Otachi

    Theor. Comput. Sci.   772 巻   頁: 111 - 122   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2018.11.024

    researchmap

  62. Token Sliding on Split Graphs. 査読有り 国際共著

    Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora

    Leibniz International Proceedings in Informatics   126 巻   頁: 13:1-13:17   2019年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)  

    DOI: 10.4230/LIPIcs.STACS.2019.13

  63. Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity 査読有り 国際共著

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Algorithmica   80 巻 ( 7 ) 頁: 2160 - 2180   2018年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer New York LLC  

    The problem MaxW-Light (MaxW-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MaxW-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MaxW-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54–87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

    DOI: 10.1007/s00453-017-0399-9

    Scopus

    researchmap

  64. Swapping colored tokens on graphs 査読有り 国際共著

    Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno

    Theoretical Computer Science   729 巻   頁: 1 - 10   2018年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Elsevier B.V.  

    We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,…,c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for c=3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.

    DOI: 10.1016/j.tcs.2018.03.016

    Scopus

    researchmap

  65. Reconfiguration of colorable sets in classes of perfect graphs 査読有り

    Takehiro Ito, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   101 巻   頁: 271 - 2713   2018年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (reconfiguration) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.

    DOI: 10.4230/LIPIcs.SWAT.2018.27

    Scopus

    researchmap

  66. Parameterized orientable deletion 査読有り 国際共著

    Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

    Leibniz International Proceedings in Informatics, LIPIcs   101 巻   頁: 241 - 2413   2018年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    A graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-Orientable Deletion problem: given a graph G = (V, E), delete the minimum number of vertices to make G d-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: We show that the problem is W[2]-hard and log n-inapproximable with respect to k, the number of deleted vertices. This closes the gap in the problem’s approximability. We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by d + k, but W-hard for each of the parameters d, k separately. We show that, under the SETH, for all d, , the problem does not admit a (d + 2 − )tw, algorithm where tw is the graph’s treewidth, resolving as a special case an open problem on the complexity of PseudoForest Deletion. We show that the problem is W-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time dO(d·cw), showing that the problem is FPT by d + cw, and improving the previously best know algorithm for this case.

    DOI: 10.4230/LIPIcs.SWAT.2018.24

    Scopus

    researchmap

  67. How Bad is the Freedom to Flood-It? 査読有り 国際共著

    Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   100 巻   頁: 51 - 513   2018年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    FIXED-FLOOD-IT and FREE-FLOOD-IT are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in FREE-FLOOD-IT the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for FIXED-FLOOD-IT become intractable for FREE-FLOOD-IT. We also show that some tractable cases for FIXED-FLOOD-IT are still tractable for FREE-FLOOD-IT but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for FIXED-FLOOD-IT is always at most twice that of FREE-FLOOD-IT, and this is tight.

    DOI: 10.4230/LIPIcs.FUN.2018.5

    Scopus

    researchmap

  68. A faster parameterized algorithm for PSEUDOFOREST DELETION 査読有り 国際共著

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Discrete Applied Mathematics   236 巻   頁: 42 - 56   2018年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Elsevier B.V.  

    A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

    DOI: 10.1016/j.dam.2017.10.018

    Scopus

    researchmap

  69. Space-effcient algorithms for longest increasing subsequence 査読有り 国際共著

    Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

    Leibniz International Proceedings in Informatics, LIPIcs   96 巻   頁: 44:1-44:15   2018年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(n log n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n = s = n, we present algorithms that use O(s log n) bits and O(1 s · n2 · log n) time for computing the length of a longest increasing subsequence, and O(1 s · n2 · log2 n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

    DOI: 10.4230/LIPIcs.STACS.2018.44

    Scopus

    researchmap

  70. Induced Minor Free Graphs: Isomorphism and Clique-Width 査読有り 国際共著

    Rémy Belmonte, Yota Otachi, Pascal Schweitzer

    Algorithmica   80 巻 ( 1 ) 頁: 29 - 47   2018年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer New York LLC  

    Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph.

    DOI: 10.1007/s00453-016-0234-8

    Scopus

    researchmap

  71. Vertex deletion problems on chordal graphs 査読有り 国際共著

    Yixin Cao, Yuping Ke, Yota Otachi, Jie You

    Leibniz International Proceedings in Informatics, LIPIcs   93 巻   頁: 22:1-22:14 - 86   2018年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

    DOI: 10.4230/LIPIcs.FSTTCS.2017.22

    Scopus

    researchmap

  72. Computational Complexity of Robot Arm Simulation Problems. 査読有り

    Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara

    Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings   10979 巻   頁: 177 - 188   2018年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-319-94667-2_15

    researchmap

  73. Exact Algorithms for the Max-Min Dispersion Problem. 査読有り

    Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa

    Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Guangzhou, China, May 8-10, 2018, Proceedings   10823 巻   頁: 263 - 272   2018年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    DOI: 10.1007/978-3-319-78455-7_20

    researchmap

  74. Vertex deletion problems on chordal graphs. 査読有り 国際共著

    Yixin Cao, Yuping Ke, Yota Otachi, Jie You

    Theoretical Computer Science   745 巻   頁: 75 - 86   2018年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    DOI: 10.1016/j.tcs.2018.05.039

    researchmap

  75. Safe sets in graphs: Graph classes and structural parameters 査読有り 国際共著

    Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Hirotaka Ono, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu

    Journal of Combinatorial Optimization   36 巻 ( 4 ) 頁: 1 - 22   2017年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Springer New York LLC  

    A safe set of a graph (Formula presented.) is a non-empty subset S of V such that for every component A of G[S] and every component B of (Formula presented.), we have (Formula presented.) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.

    DOI: 10.1007/s10878-017-0205-2

    Scopus

    researchmap

  76. Hitori numbers 査読有り

    Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno

    Journal of Information Processing   25 巻   頁: 695 - 707   2017年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Information Processing Society of Japan  

    Hitori is a popular “pencil-and-paper” puzzle defined as follows. In n-hitori, we are given an n×n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label
    Rule 2) Painted squares are never (horizontally or vertically) adjacent
    Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori number which are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number h(n) is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⌊(2n - 1)/3⌋ ≤ h(n) ≤ 2⌊n/3⌋ + 1 for n ≥ 2 and ⌊(4n2 - 4n + 11)/5⌋ ≥ h(n) ≤ (4n2 + 2n - 2)/5 for n ≤ 3.

    DOI: 10.2197/ipsjjip.25.695

    Scopus

    researchmap

  77. Extending Partial Representations of Interval Graphs 査読有り 国際共著

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh, Tomas Vyskoil

    ALGORITHMICA   78 巻 ( 3 ) 頁: 945 - 967   2017年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:SPRINGER  

    Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13: 335-379, 1976) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph G with a partial representation R' fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation R of the entire graph G extending R'. We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15: 835-855, 1965) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

    DOI: 10.1007/s00453-016-0186-z

    Web of Science

    researchmap

  78. Alliances in graphs of bounded clique-width 査読有り

    Masashi Kiyomi, Yota Otachi

    DISCRETE APPLIED MATHEMATICS   223 巻   頁: 91 - 97   2017年5月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs.
    In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number. (C) 2017 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2017.02.004

    Web of Science

    researchmap

  79. Extending Partial Representations of Proper and Unit Interval Graphs 査読有り 国際共著

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomas Vyskocil

    ALGORITHMICA   77 巻 ( 4 ) 頁: 1071 - 1104   2017年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:SPRINGER  

    The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs (Balko et al. in 2013). So unless , proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

    DOI: 10.1007/s00453-016-0133-z

    Web of Science

    researchmap

  80. A faster parameterized algorithm for pseudoforest deletion 査読有り 国際共著

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   63 巻   頁: 7:1-7:12   2017年2月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

    DOI: 10.4230/LIPIcs.IPEC.2016.7

    Scopus

    researchmap

  81. Thin strip graphs 査読有り

    Takashi Hayashi, Akitoshi Kawamura, Yota Otachi, Hidehiro Shinohara, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   216 巻   頁: 203 - 210   2017年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    A unit disk graph is a c-strip graph if it has a unit disk representation in which all centers of the unit disks lie between two parallel lines at distance c. The classes of c-strip graphs for various c are studied in the literature. For example, the 0-strip graphs are exactly the unit interval graphs, and every root 3/2-strip graph is a co-comparability graph. In this paper, we introduce the class of thin strip graphs and study their properties. A graph is a thin strip graph if it is a c-strip graph for every c &gt; 0. We show that there is no constant t such that the t-strip graphs are exactly the thin strip graphs. We also show that the class of thin strip graphs properly includes the class of mixed unit interval graphs. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.01.018

    Web of Science

    researchmap

  82. Ferrers dimension of grid intersection graphs 査読有り 国際共著

    Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara

    DISCRETE APPLIED MATHEMATICS   216 巻   頁: 130 - 135   2017年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We investigate the Ferrers dimension of classes of grid intersection graphs and show properties and characterizations. In particular, we show that (1) the grid intersection graphs form a proper subclass of the class of bipartite graphs of Ferrers dimension 4, (2) segment-ray graphs have a forbidden submatrix characterization, and (3) a bipartite graph is a unit grid intersection graph if and only if it is the intersection of two bipartite permutation graphs. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.05.035

    Web of Science

    researchmap

  83. Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph 査読有り 国際共著

    Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10392 巻   頁: 150 - 161   2017年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer Verlag  

    In this paper, we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m\\cdot \\omega (G)) for any n-vertex chordal graph with m edges, where \\omega (G) \\le n is the maximum size of a clique in G. The problem generalizes that of enumerating maximal independent sets and maximal induced forests, which correspond to respectively 0-degenerate and 1-degenerate subgraphs.

    DOI: 10.1007/978-3-319-62389-4_13

    Scopus

    researchmap

  84. Degree-constrained orientation of maximum satisfaction: Graph classes and parameterized complexity 査読有り 国際共著

    Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

    Leibniz International Proceedings in Informatics, LIPIcs   64 巻   頁: 20.1 - 20.12   2016年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-LIGHT is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MAX W-HEAVY can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin, Todinca, and Villanger [SIAM J. Comput., 44(1):57-87, 2015]. The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

    DOI: 10.4230/LIPIcs.ISAAC.2016.20

    Scopus

    researchmap

  85. On the classes of interval graphs of limited nesting and count of lengths 査読有り 国際共著

    Pavel Klavík, Yota Otachi, Jiří Šejnoha

    Leibniz International Proceedings in Informatics, LIPIcs   64 巻   頁: 45.1 - 45.13   2016年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called k-length interval graphs were considered in which the number of different lengths of intervals is limited by k. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for k = 2. We propose generalizations of proper interval graphs called k-nested interval graphs in which there are no chains of k + 1 intervals nested in each other. It is easy to see that k-nested interval graphs are a superclass of k-length interval graphs. We give a linear-time recognition algorithm for k-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is FPT with respect to the nesting k and the length of the formula, while the problem is W[2]-hard when parameterized just by the length of the formula. Further, we show that a generalization of recognition called partial representation extension is polynomial-time solvable for k-nested interval graphs, while it is NP-hard for k-length interval graphs, even when k = 2.

    DOI: 10.4230/LIPIcs.ISAAC.2016.45

    Scopus

    researchmap

  86. Finding a chain graph in a bipartite permutation graph 査読有り

    Masashi Kiyomi, Yota Otachi

    INFORMATION PROCESSING LETTERS   116 巻 ( 9 ) 頁: 569 - 573   2016年9月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We present a polynomial-time algorithm for solving SUBGRAPH ISOMORPHISM where the base graphs are bipartite permutation graphs and the pattern graphs are chain graphs. (C) 2016 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.ip1.2016.04.006

    Web of Science

    researchmap

  87. A lower bound on opaque sets 査読有り 国際共著

    Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, János Pach

    Leibniz International Proceedings in Informatics, LIPIcs   51 巻   頁: 46.1 - 46.10   2016年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

    It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.

    DOI: 10.4230/LIPIcs.SoCG.2016.46

    Scopus

    researchmap

  88. Polynomial-time algorithms for SUBGRAPH ISOMORPHISM in small graph classes of perfect graphs 査読有り

    Matsuo Konagaya, Yota Otachi, Ryuhei Uehara

    DISCRETE APPLIED MATHEMATICS   199 巻   頁: 37 - 45   2016年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Given two graphs, SUBGRAPH ISOMORPHISM is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time.
    In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.01.040

    Web of Science

    researchmap

  89. A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares 査読有り

    Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS   51 巻   頁: 25 - 39   2016年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.comgeo.2015.10.004

    Web of Science

    researchmap

  90. On the treewidth of toroidal grids 査読有り

    Masashi Kiyomi, Yoshio Okamoto, Yota Otachi

    DISCRETE APPLIED MATHEMATICS   198 巻   頁: 303 - 306   2016年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the n x n toroidal grid is either 2n - 2 or 2n - 1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2015.06.027

    Web of Science

    researchmap

  91. Induced Minor Free Graphs: Isomorphism and Clique-width 査読有り 国際共著

    Remy Belmonte, Yota Otachi, Pascal Schweitzer

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   9224 巻   頁: 299 - 311   2016年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is isomorphism complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. Those two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor or subgraph.

    DOI: 10.1007/978-3-662-53174-7_21

    Web of Science

    researchmap

  92. Safe sets in graphs: Graph classes and structural parameters 査読有り 国際共著

    Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10043 巻   頁: 241 - 253   2016年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer Verlag  

    A safe set of a graph G = (V,E) is a non-empty subset S of V such that for every component A of G[S] and every component B of G[V \\ S], we have |A| ≥ |B| whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

    DOI: 10.1007/978-3-319-48749-6_18

    Scopus

    researchmap

  93. Linear-time algorithm for sliding tokens on trees 査読有り 国際共著

    Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

    THEORETICAL COMPUTER SCIENCE   600 巻   頁: 132 - 142   2015年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar l(b)vertical bar =vertical bar I-r vertical bar and imagine that a token is placed on each vertex in I-b. Then, the SLIDING TOKEN problem is to determine whether there exists a sequence of independent sets which transforms I-b into I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I-b and I-r whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2015.07.037

    Web of Science

    researchmap

  94. Extending partial representations of subclasses of chordal graphs 査読有り 国際共著

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh

    THEORETICAL COMPUTER SCIENCE   576 巻   頁: 85 - 101   2015年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees of T'. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged).
    We consider four modifications of T' leading to vastly different problems: (i) T = T', (ii) T is a subdivision of T', (iii) T is a supergraph of T', and (iv) T' is a topological minor of T. In some cases, it is interesting to consider the complexity even when just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components of the input graph G and the size of the tree T'.
    We describe an interesting relation with integer partition problems. The problem 3-PARTITION is used for all NP-completeness reductions. When the space in T' is limited, partial representation extension of proper interval graphs is "equivalent" to the BINPACKING problem. (C) 2015 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2015.02.007

    Web of Science

    researchmap

  95. Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds 査読有り 国際共著

    Kazuyuki Amano, Kyaw May Oo, Yota Otachi, Ryuhei Uehara

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   E98D 巻 ( 3 ) 頁: 486 - 489   2015年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

    Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time ismuch faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.

    DOI: 10.1587/transinf.2014FCP0007

    Web of Science

    researchmap

    その他リンク: http://dblp.uni-trier.de/db/journals/ieicet/ieicet98d.html#journals/ieicet/AmanoOOU15

  96. Swapping colored tokens on graphs 査読有り 国際共著

    Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9214 巻   頁: 619 - 628   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer Verlag  

    We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2,..., c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for every constant c ≥ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees.

    DOI: 10.1007/978-3-319-21840-3_51

    Scopus

    researchmap

  97. COMPLETELY INDEPENDENT SPANNING TREES IN (PARTIAL) k-TREES 査読有り

    Masayoshi Matsushita, Yota Otachi, Toru Araki

    DISCUSSIONES MATHEMATICAE GRAPH THEORY   35 巻 ( 3 ) 頁: 427 - 437   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:UNIV ZIELONA GORA  

    Two spanning trees T-1 and T-2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T-1 and T-2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree.
    First we show that [k/2] &lt;= cist(G) &lt;= k - 1 for any k-tree G. Then we show that for any p is an element of {[k/2],..., k - 1}, there exist infinitely many k-trees G such that cist(G) = p. Finally we consider algorithmic aspects for computing cist(G). Using Courcelle's theorem, we show that there is a linear-time algorithm that computes cist(G) for a partial k-tree, where k is a fixed constant.

    DOI: 10.7151/dmgt.1806

    Web of Science

    researchmap

  98. Competitive diffusion on weighted graphs 査読有り

    Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9214 巻   頁: 422 - 433   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer Verlag  

    Consider an undirected and vertex-weighted graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her idea which spreads along the edges in the graph. The objective of every player is to maximize the sum of weights of vertices infected by his/her idea. In this paper, we study a computational problem of asking whether a pure Nash equilibrium exists in a given graph, and present several negative and positive results with regard to graph classes. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudo-polynomial time
    and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.

    DOI: 10.1007/978-3-319-21840-3_35

    Scopus

    researchmap

  99. Reconfiguration of Cliques in a Graph 査読有り

    Takehiro Ito, Hirotaka Ono, Yota Otachi

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015)   9076 巻   頁: 212 - 223   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. In particular, the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.

    DOI: 10.1007/978-3-319-17142-5_19

    Web of Science

    researchmap

  100. Sliding Token on Bipartite Permutation Graphs 査読有り 国際共著

    Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, Ryuhei Uehara

    ALGORITHMS AND COMPUTATION, ISAAC 2015   9472 巻   頁: 237 - 247   2015年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER INT PUBLISHING AG  

    Sliding Token is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that Sliding Token is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for Sliding Token on bipartite permutation and bipartite distance-hereditary graphs.

    DOI: 10.1007/978-3-662-48971-0_21

    Web of Science

    researchmap

  101. Base-object location problems for base-monotone regions 査読有り

    Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

    THEORETICAL COMPUTER SCIENCE   555 巻   頁: 71 - 84   2014年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given baselines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n x n pixel grid. We then present an O (n(3))-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. (C) 2013 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2013.11.030

    Web of Science

    researchmap

  102. Efficient algorithms for network localization using cores of underlying graphs 査読有り

    Meng Li, Yota Otachi, Takeshi Tokuyama

    THEORETICAL COMPUTER SCIENCE   553 巻   頁: 18 - 26   2014年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Network localization is important for networks with no prefixed positions of network nodes such as sensor networks. We are given a subset of the set of ((n)(2)) pairwise distances among n sensors in some Euclidean space. We want to determine the positions of each sensor from the (partial) distance information. The input can be seen as an edge weighted graph. In this paper, we present some efficient algorithms that solve this problem using the structures of input graphs, which we call their cores. For instance, we present a polynomial-time algorithm solving the network localization problem for graphs with connected dominating sets of bounded size. This algorithm allows us to have fixed-parameter tractable algorithms for some restricted instances such as graphs with connected vertex covers of bounded size. (C) 2014 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2014.02.020

    Web of Science

    researchmap

  103. A 4.31-approximation for the geometric unique coverage problem on unit disks 査読有り

    Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    THEORETICAL COMPUTER SCIENCE   544 巻   頁: 14 - 31   2014年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 +4/root 3+epsilon (&lt;4.3095+epsilon) for any fixed constant epsilon&gt;0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2014 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2014.04.014

    Web of Science

    researchmap

  104. Approximating the path-distance-width for AT-free graphs and graphs in related classes 査読有り

    Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   168 巻   頁: 69 - 77   2014年5月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We consider the problem of determining the path-distance-width for AT-free graphs and graphs in related classes such as k-cocomparability graphs, proper interval graphs, cobipartite graphs, and cochain graphs. We first show that the problem is NP-hard even for cobipartite graphs, and thus for AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for AT-free graphs and graphs in the related graph classes mentioned above. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for cochain graphs, which form a subclass of the class of proper interval graphs.(c) 2012 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2012.11.015

    Web of Science

    researchmap

  105. Lower bounds for treewidth of product graphs 査読有り

    Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   162 巻   頁: 251 - 258   2014年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Two lower bounds for the treewidth of product graphs are presented in terms of the bramble number. The first bound is that the bramble number of the Cartesian product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the PI number of G(2), where the PI number is a new graph parameter introduced in this paper. The second bound is that the bramble number of the strong product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the bramble number of G(2). We also demonstrate applications of the lower bounds. (C) 2013 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2013.08.005

    Web of Science

    researchmap

  106. Intersection Dimension of Bipartite Graphs 査読有り 国際共著

    Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014)   8402 巻   頁: 323 - 340   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We introduce a concept of intersection dimension of a graph with respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes defined as intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graph-theoretic results, we show that the recognition problems for certain graph classes are NP-complete.

    DOI: 10.1007/978-3-319-06089-7_23

    Web of Science

    researchmap

  107. Polynomial-Time Algorithms for SUBGRAPH ISOMORPHISM in Small Graph Classes of Perfect Graphs 査読有り

    Matsuo Konagaya, Yota Otachi, Ryuhei Uehara

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014)   8402 巻   頁: 216 - 228   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second graph (the pattern graph). This problem is NP-complete for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time.
    In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. [Discrete Math. 312, pp. 3164-3173, 2012]. To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete.

    DOI: 10.1007/978-3-319-06089-7_15

    Web of Science

    researchmap

  108. Reduction Techniques for Graph Isomorphism in the Context of Width Parameters 査読有り 国際共著

    Yota Otachi, Pascal Schweitzer

    ALGORITHM THEORY - SWAT 2014   8503 巻   頁: 368 - +   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We study the parameterized complexity of the graph isomorphism problem when parameterized by width parameters related to tree decompositions. We apply the following technique to obtain fixed-parameter tractability for such parameters. We first compute an isomorphism invariant set of potential bags for a decomposition and then apply a restricted version of the Weisfeiler-Lehman algorithm to solve isomorphism. With this we show fixed-parameter tractability for several parameters and provide a unified explanation for various isomorphism results concerned with parameters related to tree decompositions.
    As a possibly first step towards intractability results for parameterized graph isomorphism we develop an fpt Turing-reduction from strong tree width to the a priori unrelated parameter maximum degree.

    DOI: 10.1007/978-3-319-08404-6_32

    Web of Science

    researchmap

  109. Extending Partial Representations of Proper and Unit Interval Graphs 査読有り 国際共著

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomas Vyskocil

    ALGORITHM THEORY - SWAT 2014   8503 巻   頁: 253 - +   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations.
    We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for a special class of instances, where the ordering of the connected components of the input graph along the real line is fixed. This includes the case of partial representation extension.
    The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs [Balko et al. ISAAC'13]. So unless P = NP, proper and unit interval representations have very different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

    DOI: 10.1007/978-3-319-08404-6_22

    Web of Science

    researchmap

  110. Depth-First Search Using O(n) Bits 査読有り 国際共著

    Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara

    ALGORITHMS AND COMPUTATION, ISAAC 2014   8889 巻   頁: 553 - 564   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space.

    DOI: 10.1007/978-3-319-13075-0_44

    Web of Science

    researchmap

  111. Polynomial-Time Algorithm for Sliding Tokens on Trees 査読有り 国際共著

    Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

    ALGORITHMS AND COMPUTATION, ISAAC 2014   8889 巻   頁: 389 - 400   2014年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar I-b vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-b. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I-b and I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets between I-b and I-r whose length (i. e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length.

    DOI: 10.1007/978-3-319-13075-0_31

    Web of Science

    researchmap

  112. Base location problems for base-monotone regions 査読有り

    Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   7748 巻   頁: 53 - 64   2013年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n3)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. © 2013 Springer-Verlag.

    DOI: 10.1007/978-3-642-36065-7_7

    Scopus

    researchmap

  113. On complexity of flooding games on graphs with interval representations 査読有り

    Hiroyuki Fukui, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8296 巻   頁: 73 - 84   2013年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    The flooding games, which are called Flood-It, Mad Virus, or HoneyBee, are a kind of coloring games and they have been becoming popular online. In these games, each player colors one specified cell in his/her turn, and all connected neighbor cells of the same color are also colored by the color. This flooding or coloring spreads on the same color cells. It is natural to consider the coloring games on general graphs: Once a vertex is colored, the flooding flows along edges in the graph. Recently, computational complexities of the variants of the flooding games on several graph classes have been studied. We investigate the one player flooding games on some graph classes characterized by interval representations. Our results state that the number of colors is a key parameter to determine the computational complexity of the flooding games. © 2013 Springer-Verlag.

    DOI: 10.1007/978-3-642-45281-9_7

    Scopus

    researchmap

  114. Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes 査読有り 国際共著

    Yota Otachi, Pascal Schweitzer

    ALGORITHMS AND COMPUTATION   8283 巻   頁: 111 - 118   2013年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We study the graph isomorphism problem for graph classes defined by sets of forbidden subgraphs. We show that there is a complexity dichotomy in case the set of forbidden subgraphs is finite. More precisely, we show that the problem is polynomial-time solvable if the forbidden set contains a forest of subdivided stars and is graph isomorphism complete otherwise. We also show that, assuming that the graph isomorphism problem is not polynomial-time solvable in general, there is no such dichotomy for the cases of infinite sets of forbidden subgraphs. To this end, we conditionally show that there exists a graph class closed under taking subgraphs with intermediate isomorphism problem, i.e., a class on which the isomorphism problem is neither polynomial-time solvable nor graph isomorphism complete.

    DOI: 10.1007/978-3-642-45030-3_11

    Web of Science

    researchmap

  115. THE PATH-DISTANCE-WIDTH OF HYPERCUBES 査読有り

    Yota Otachi

    DISCUSSIONES MATHEMATICAE GRAPH THEORY   33 巻 ( 2 ) 頁: 467 - 470   2013年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:UNIV ZIELONA GORA  

    The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S subset of V(G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i.
    In this note, we determine the path-distance-width of hypercubes.

    DOI: 10.7151/dmgt.1682

    Web of Science

    researchmap

  116. Bounded representations of interval and proper interval graphs 査読有り 国際共著

    Martin Balko, Pavel Klavík, Yota Otachi

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8283 巻   頁: 535 - 546   2013年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    Klavík et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals ℒv and ℛv called bounds. We ask whether there exists a bounded representation in which each interval Iv has its left endpoint in ℒv and its right endpoint in . We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly, the bounded representation problem is polynomially solvable for proper interval graphs and NP-complete for unit interval graphs [Klavík et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of G satisfying some additional constraints. The bounded representation problems generalize many of these problems. © 2013 Springer-Verlag.

    DOI: 10.1007/978-3-642-45030-3_50

    Scopus

    researchmap

  117. Subgraph isomorphism in graph classes 査読有り

    Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno

    DISCRETE MATHEMATICS   312 巻 ( 21 ) 頁: 3164 - 3173   2012年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We investigate the computational complexity of the following restricted variant of SUBGRAPH ISOMORPHISM: given a pair of connected graphs G = (V-G, E-G) and H = (V-H, E-H), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of SUBGRAPH ISOMORPHISM such as HAMILTONIAN PATH, CLIQUE, BANDWIDTH, and GRAPH ISOMORPHISM can be solved in polynomial time, while these problems are hard in general. (c) 2012 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2012.07.010

    Web of Science

    researchmap

  118. Parameterized Complexity of the Spanning Tree Congestion Problem 査読有り 国際共著

    Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi, Erik Jan van Leeuwen

    ALGORITHMICA   64 巻 ( 1 ) 頁: 85 - 111   2012年9月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:SPRINGER  

    We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed ka parts per thousand yen8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for ka parts per thousand currency sign3 the problem becomes polynomially time solvable.

    DOI: 10.1007/s00453-011-9565-7

    Web of Science

    researchmap

  119. Efficient enumeration of ordered trees with k leaves 査読有り

    Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

    THEORETICAL COMPUTER SCIENCE   442 巻   頁: 22 - 27   2012年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    This paper presents a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time per tree, whereas our algorithm generates such trees in O(1) time per tree in the worst case. (C) 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2011.01.017

    Web of Science

    researchmap

  120. Enumerating All Rooted Trees Including k Leaves 査読有り

    Masanobu Ishikawa, Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   E95D 巻 ( 3 ) 頁: 763 - 768   2012年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

    This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3], [6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all "ordered" trees with 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.

    DOI: 10.1587/transinf.E95.D.763

    Web of Science

    researchmap

    その他リンク: http://dblp.uni-trier.de/db/journals/ieicet/ieicet95d.html#journals/ieicet/IshikawaYON12

  121. Random generation and enumeration of bipartite permutation graphs 査読有り

    Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara

    Journal of Discrete Algorithms   10 巻 ( 1 ) 頁: 84 - 97   2012年1月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on reverse search, and it outputs each connected bipartite permutation graph in O(1) time. © 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.jda.2011.11.001

    Scopus

    researchmap

  122. A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks 査読有り

    Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    ALGORITHMS AND COMPUTATION, ISAAC 2012   7676 巻   頁: 372 - 381   2012年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 + 4/root 3 + epsilon (&lt; 4.3095 + epsilon) for any fixed constant epsilon &gt; 0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound.

    DOI: 10.1007/978-3-642-35261-4_40

    Web of Science

    researchmap

  123. On bipartite powers of bigraphs 査読有り

    Yoshio Okamoto, Yota Otachi, Ryuhei Uehara

    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE   14 巻 ( 2 ) 頁: 11-20   2012年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

  124. A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares 査読有り

    Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   7357 巻   頁: 24 - 35   2012年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Springer  

    We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen (2009) before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. © 2012 Springer-Verlag.

    DOI: 10.1007/978-3-642-31155-0_3

    Scopus

    researchmap

  125. Isomorphism for Graphs of Bounded Connected-Path-Distance-Width 査読有り

    Yota Otachi

    ALGORITHMS AND COMPUTATION, ISAAC 2012   7676 巻   頁: 455 - 464   2012年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We show that Graph Isomorphism problem (GI) can be solved in O(n(2)) time for graphs of bounded connected-path-distance-width, and more generally, in O(n(c+1)) time for graphs of bounded c-connected-path-distance-width, where n is the number of vertices. These results extend the result of Yamazaki, Bodlaender, de Fluiter, and Thilikos [Isomorphism for graphs of bounded distance width. Algorithmica 24, 105-127 (1999)], who showed the fixed-parameter tractability of GI parameterized by rooted-path-distance-width.

    DOI: 10.1007/978-3-642-35261-4_48

    Web of Science

    researchmap

  126. Extending Partial Representations of Subclasses of Chordal Graphs 査読有り 国際共著

    Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh

    ALGORITHMS AND COMPUTATION, ISAAC 2012   7676 巻   頁: 444 - 454   2012年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    Chordal graphs are intersection graphs of subtrees in a tree. We investigate complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (keeps the pre-drawn subtrees unchanged).
    We consider four modifications of T' and get vastly different problems. In some cases, the problem is interesting even if just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization.
    In addition, we study parametrized complexity by the number of pre-drawn subtrees, the number of components and the size of the tree T'. We describe an interesting relation with integer partition problems. The problem 3-Partition is used in the NP-completeness reductions. The BIN-PACKING problem is closely related to the extension of interval graphs when space in T' is limited, and we obtain "equivalency" with BIN PACKING.

    DOI: 10.1007/978-3-642-35261-4_47

    Web of Science

    researchmap

  127. Spanning tree congestion of k-outerplanar graphs 査読有り 国際共著

    Hans L. Bodlaender, Kyohei Kozawa, Takayoshi Matsushima, Yota Otachi

    DISCRETE MATHEMATICS   311 巻 ( 12 ) 頁: 1040 - 1045   2011年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    In 1987, Simonson conjectured that every k-outerplanar graph of maximum degree d has spanning tree congestion at most k . d [S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20(1987)235-252]. We show that his conjecture is true and the bound is tight for outerplanar graphs and k-outerplanar graphs of maximum degree 4. We give a precise characterization of the spanning tree congestion of outerplanar graphs, and thus show that the spanning tree congestion of outerplanar graphs can be determined in linear time. (C) 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2011.03.002

    Web of Science

    researchmap

  128. Bandwidth and pathwidth of three-dimensional grids 査読有り

    Yota Otachi, Ryohei Suda

    DISCRETE MATHEMATICS   311 巻 ( 10-11 ) 頁: 881 - 887   2011年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors. (C) 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2011.02.019

    Web of Science

    researchmap

  129. Hardness results and an exact exponential algorithm for the spanning tree congestion problem 査読有り

    Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno

    Journal of Graph Algorithms and Applications   15 巻 ( 6 ) 頁: 727 - 751   2011年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential- time) exact algorithm that runs in O*(2 n) time, where n denotes the number of vertices. Additionally, we present simple combinatorial lem- mas, which yield a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

    DOI: 10.7155/jgaa.00246

    Scopus

    researchmap

  130. Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem 査読有り

    Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011   6648 巻   頁: 452 - 462   2011年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential-time) exact algorithm that runs in O*(2(n)) time, where n denotes the number of vertices. Additionally, we provide a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

    DOI: 10.1007/978-3-642-20877-5_44

    Web of Science

    researchmap

  131. Spanning tree congestion of rook's graphs 査読有り

    Kyohei Kozawa, Yota Otachi

    Discussiones Mathematicae - Graph Theory   31 巻 ( 4 ) 頁: 753 - 761   2011年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:University of Zielona Gora  

    Let G be a connected graph and T be a spanning tree of G. For e ∈ E(T ), the congestion of e is the number of edges in G joining the two components of T - e. The congestion of T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion over all its spanning trees. In this paper, we determine the spanning tree congestion of the rook's graph Km Kn for any m and n.

    DOI: 10.7151/dmgt.1577

    Scopus

    researchmap

  132. Approximability of the Path-Distance-Width for AT-free Graphs 査読有り

    Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   6986 巻   頁: 271 - +   2011年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs.

    DOI: 10.1007/978-3-642-25870-1_25

    Web of Science

    researchmap

  133. The carving-width of generalized hypercubes 査読有り

    Yohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE MATHEMATICS   310 巻 ( 21 ) 頁: 2867 - 2876   2010年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    The carving-width of a graph is the minimum congestion of routing trees for the graph. We determine the carving-width of generalized hypercubes: Hamming graphs, even grids, and tori. Our results extend the result of Chandran and Kavitha [L.S. Chandran, T. Kavitha, The carvingwidth of hypercubes, Discrete Math. 306 (2006) 2270-2274] that determines the carving-width of hypercubes. (C) 2010 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2010.06.039

    Web of Science

    researchmap

  134. Complexity Results for the Spanning Tree Congestion Problem 査読有り 国際共著

    Yota Otachi, Hans L. Bodlaender, Erik Jan van Leeuwen

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE   6410 巻   頁: 3 - +   2010年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the complexity of this problem. First, we show that for every fixed k and d the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k &gt;= 10. For very small values of k however, the problem becomes polynomially solvable. We also show that it is NP-hard to approximate the spanning tree congestion within a factor better than 11/10. On planar graphs, we prove the problem is NP-hard in general, but solvable in linear time for fixed k.

    DOI: 10.1007/978-3-642-16926-7_3

    Web of Science

    researchmap

  135. On spanning tree congestion of graphs 査読有り

    Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE MATHEMATICS   309 巻 ( 13 ) 頁: 4215 - 4224   2009年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Let G be a connected graph and T be a spanning tree of G. For e is an element of E(T), the congestion of e is the number of edges in G connecting two components of T - e. The edge congestion of G in T is the maximum congestion over all edges in T. The spanning tree congestion of G is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes. (C) 2008 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2008.12.021

    Web of Science

    researchmap

  136. Security number of grid-like graphs 査読有り

    Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   157 巻 ( 11 ) 頁: 2555 - 2561   2009年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    The security number of a graph is the cardinality of a smallest vertex subset of the graph Such that any attack on the subset is defendable. In this paper, we determine the security number of two-dimensional cylinders and tori. This result settles a conjecture of Brigham et al. [R.C. Brigham, R.D. Dutton, S.T. Hedetniemi, Security in graphs, Discrete Appl. Math. 155(2007)1708-1714]. (C) 2009 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2009.03.020

    Web of Science

    researchmap

  137. Efficient Enumeration of Ordered Trees with k Leaves 査読有り

    Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS   5431 巻   頁: 141 - +   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    In this paper, we give a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time for each, while our algorithm generates Such trees in O(1) time for each in worst case.

    DOI: 10.1007/978-3-642-00202-1_13

    Web of Science

    researchmap

  138. Random Generation and Enumeration of Bipartite Permutation Graphs 査読有り

    Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   5878 巻   頁: 1104 - +   2009年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:SPRINGER-VERLAG BERLIN  

    Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected bipartite permutation graph in O(1) time.

    DOI: 10.1007/978-3-642-10631-6_111

    Web of Science

    researchmap

  139. An improved algorithm for the longest induced path problem on k-chordal graphs 査読有り

    Tetsuya Ishizeki, Yota Otachi, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   156 巻 ( 15 ) 頁: 3057 - 3059   2008年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    Gavril [F. Gavril, Algorithms for maximum weight induced paths, Information Processing Letters 81 (2002) 203-208] showed that the length of a longest induced path for graphs having no induced cycles on more than k vertices can be computed in O(n(k)m) time where n and m denote the number of vertices and edges, respectively. In this paper, we present an O(n(k)) time algorithm for the same problem. (C) 2008 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2008.01.019

    Web of Science

    researchmap

  140. A lower bound for the vertex boundary-width of complete k-ary trees 査読有り

    Yota Otachi, Koichi Yamazaki

    DISCRETE MATHEMATICS   308 巻 ( 12 ) 頁: 2389 - 2395   2008年6月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    The vertex boundary-width problem (for short VBWP) is to determine the value of vbw(G) = max(1 &lt;= l &lt;= vertical bar V vertical bar) min (S subset of V,vertical bar S vertical bar=l)vertical bar N(S)vertical bar for a given graph G = (V, E), where N(S) = {upsilon is not an element of S vertical bar upsilon is a neighbor of u for some u is an element of S}. In this paper, we give a lower bound for vertex boundary-width of complete k-ary trees. (C) 2007 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2007.05.014

    Web of Science

    researchmap

  141. Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs 査読有り

    Yota Otachi, Yoshio Okamoto, Koichi Yamazaki

    DISCRETE APPLIED MATHEMATICS   155 巻 ( 17 ) 頁: 2383 - 2390   2007年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:ELSEVIER SCIENCE BV  

    We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P-6-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable. (C) 2007 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2007.07.010

    Web of Science

    researchmap

▼全件表示

MISC 1

  1. 正則誘導部分グラフ遷移問題の計算複雑さ

    江藤宏, 伊藤健洋, 小林靖明, 大舘陽太, 和佐州洋  

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集2022 巻   2022年

     詳細を見る

講演・口頭発表等 12

  1. Exploring the gap between treedepth and vertex cover through vertex integrity 国際会議

    Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

    The 12th International Conference on Algorithms and Complexity (CIAC 2021) 

     詳細を見る

    開催年月日: 2021年5月

    記述言語:英語   会議種別:口頭発表(一般)  

  2. Fair MSO evaluation problems parameterized by vertex integrity

    2021年3月10日 

     詳細を見る

    開催年月日: 2021年3月

    記述言語:英語   会議種別:口頭発表(一般)  

  3. Finding diverse trees, paths, and more 国際会議

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi

    The 35th AAAI Conference on Artificial Intelligence (AAAI 2021) 

     詳細を見る

    開催年月日: 2021年2月

    記述言語:英語   会議種別:ポスター発表  

  4. 黒どこに対する物理ゼロ知識証明プロトコル

    2021年2月3日 

     詳細を見る

    開催年月日: 2021年2月

    記述言語:日本語   会議種別:口頭発表(一般)  

  5. Parameterized complexity of graph burning 国際会議

    Yasuaki Kobayashi, Yota Otachi

    The 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) 

     詳細を見る

    開催年月日: 2020年12月

    記述言語:英語   会議種別:口頭発表(一般)  

  6. An improved deterministic parameterized algorithm for cactus vertex deletion

    2020年12月4日 

     詳細を見る

    開催年月日: 2020年12月

    記述言語:英語   会議種別:口頭発表(一般)  

  7. Algorithms for Finding Diverse Subgraphs

    2020年9月30日 

     詳細を見る

    開催年月日: 2020年9月

    記述言語:英語   会議種別:口頭発表(一般)  

  8. Grundy distinguishes treewidth from pathwidth 国際共著 国際会議

    Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi

    The 28th European Symposium on Algorithms (ESA 2020) 

     詳細を見る

    開催年月日: 2020年9月

    記述言語:英語   会議種別:口頭発表(一般)  

  9. Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs 国際会議

    Taisuke Izumi, Yota Otachi

    The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020) 

     詳細を見る

    開催年月日: 2020年7月

    記述言語:英語   会議種別:口頭発表(一般)  

  10. Linear-time recognition of double-threshold graphs 国際会議

    Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

    The 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020) 

     詳細を見る

    開催年月日: 2020年6月

    記述言語:英語   会議種別:口頭発表(一般)  

  11. Parameterized complexity of (A, ℓ)-path packing 国際共著 国際会議

    Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

    The 31st International Workshop on Combinatorial Algorithms (IWOCA 2020) 

     詳細を見る

    開催年月日: 2020年6月

    記述言語:英語   会議種別:口頭発表(一般)  

  12. Hedonic seat arrangement problems (Extended abstract) 国際共著 国際会議

    Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

    The 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2020) 

     詳細を見る

    開催年月日: 2020年5月

    記述言語:英語   会議種別:口頭発表(一般)  

▼全件表示

共同研究・競争的資金等の研究課題 3

  1. パラメータ化近似グラフアルゴリズムのさらなる発展

    2019年4月 - 現在

    二国間交流事業共同研究 

    大舘陽太

      詳細を見る

    資金種別:競争的資金

  2. 木構造を用いたネットワーク上での計算: 理論と実践

    2018年4月 - 2019年3月

    二国間交流事業セミナー 

    大舘陽太

      詳細を見る

    資金種別:競争的資金

  3. パラメータ化近似グラフアルゴリズム

    2017年4月 - 2019年3月

    二国間交流事業共同研究 

    大舘陽太

      詳細を見る

    資金種別:競争的資金

科研費 11

  1. 超スマート社会時代のアルゴリズム工学 - パラメータ化近似均衡計算

    研究課題/研究課題番号:22H00513  2022年4月 - 2027年3月

    科学研究費助成事業  基盤研究(A)

    小野 廣隆, 柳浦 睦憲, 大舘 陽太, 脊戸 和寿, 土中 哲秀

      詳細を見る

    担当区分:研究分担者 

    均衡解は多主体最適化系における安定解であり,超スマート社会における混雑・衝突の予測・制御における鍵となる概念である.本研究では,これまで最適解発見を主な対象としていたアルゴリズム設計論の対象を均衡解発見へと発展・拡大する.通常の最適化がNP, coNPに属するのに対し均衡発見はΣ2, Π2といった多項式階層におけるより上位の計算量クラス,あるいは近傍探索におけるPLS, PPADといった計算クラスに属するため,従来型の最適化研究を超えた新たな計算量理論の展開が必要となる.本研究では,超スマート社会における基盤技術を提供する,パラメータ化計算量に基づく新たなアルゴリズム工学の確立を目指す.

  2. 固定パラメータ困難問題に対する汎用解法の研究

    研究課題/研究課題番号:18K11169  2018年4月 - 2023年3月

    科学研究費助成事業  基盤研究(C)

    清見 礼, 大舘 陽太

      詳細を見る

    担当区分:研究分担者  資金種別:競争的資金

    配分額:2340000円 ( 直接経費:1800000円 、 間接経費:540000円 )

    グラフ上の問題で解くことが難しい問題に対して、グラフが木に近い構造をしていれば速に解けるということがよくある。しかしグラフが木に近くてもなお解くことが難しい問題というものも知られている。そのような場合に、どのようなことを考えれば高速なアルゴリズムを作ることができるかをなるべく一般的な形で解明するというのが本研究の主眼である。
    研究期間を通じて、今まであまり注目されてこなかったパラメータに関するアルゴリズムを開発してきた。これにより、グラフにどのような性質があると困難な問題であっても高速なアルゴリズムを開発できるかを、今までより一般的な形で示すことができた。
    木幅が小さいグラフにおいて解くことが難しい問題について、より制限を厳しくし、頂点被覆というパラメータが小さい場合に高速に動作するアルゴリズムを考えることがある。しかし頂点被覆が小さいグラフというのはまれである。そこで木幅と頂点被覆の間にあるパラメータに関するアルゴリズムを考えることで、頂点被覆が小さいグラフよりもより一般的なグラフについて対処することが可能になった。また問題の難しさの本質がどこにあるのかの理解がより進んだ。

  3. グラフ構造パラメータ階層の詳細化による精緻なアルゴリズム設計と計算量解析

    研究課題/研究課題番号:21K11752  2021年4月 - 2026年3月

    日本学術振興会  科学研究費助成事業  基盤研究(C)

    大舘 陽太

      詳細を見る

    担当区分:研究代表者 

    配分額:4160000円 ( 直接経費:3200000円 、 間接経費:960000円 )

    グラフ上で定義される多くの問題は計算量理論上難しいことが分かっている.そのような問題に対し,グラフの分解可能性をあらわす構造パラメータを用いたアルゴリズム設計が有効である.木分解の幅によって定義される木幅がその代表的な成功例であるが,研究の発展により,一般の木分解では手に負えない問題が見つかってきている.本研究では,木分解に関連したグラフ構造パラメータの階層を見直し,グラフ分解への制限を大幅に弱めた構造パラメータを導入することで,高速アルゴリズム設計可能範囲を拡大することを目指す.さらに,既知の困難性をさらに強い制限の下で示すことにより,重要問題に対するきめ細やかな知見獲得を目指す.
    グラフ構造パラメータが作る計算量階層の詳細化によるアルゴリズム設計と計算量解析を研究し,主に以下の成果を得た.
    ・これまでに得られている頂点インテグリティに対するアルゴリズムの一部を統一して一般化するアルゴリズム的メタ定理を示した.単項二階論理で記述できる問題に対する木幅を用いたアルゴリズム的メタ定理(Courcelleの定理)が有名だが,本結果は対象範囲を木幅限定グラフからから頂点インテグリティ限定グラフに狭める一方,扱える問題を大幅に広げるものである.また,様々な問題がこのアルゴリズム的メタ定理で解決できることも示した.特に,Defective彩色問題や,種々の最小アライアンス発見問題が頂点インテグリティによるFPTアルゴリズムをもつことを初めて示した.
    ・組合せ遷移問題に対してグラフ構造パラメータに関する研究を行い,結果として様々問題を一度に解決するアルゴリズム的メタ定理を示した.ここでも単項二階論理を用い,近傍多様性というグラフ構造パラメータに関する結果を示した.また,木深度に関してもアルゴリズム的メタ定理を示すとともに,その一般化の限界を与える困難性も示した.
    ・有向グラフ上での独立集合スライディング問題を導入し,様々な場合の計算量を解明した.特に,木を向きづけしたグラフに対してこの問題が多項式時間で解けることを示した.
    ・グラフ上のトークンの逐次交換問題を研究し,これまでに知られていた多項式時間可解性をすべて含む一般的な解法を与えた.また,NP困難性を示すための一般的な定理も与え,弦グラフなどに対する困難性がそこから導かれることも示した.
    本課題の中心的研究対象である頂点インテグリティに関し,あるアルゴリズム的メタ定理を示すことができた.これは,これまでに得られている頂点インテグリティに対するアルゴリズムの一部を統一して一般化するもので,今後の研究においての理論的基礎を与えるものである.
    ここまでに得られた頂点インテグリティに関するアルゴリズム的メタ定理の適用範囲の拡大またはその限界の解明を行っていく.また,組合せ遷移問題に関するアルゴリズム的メタ定理をさらに研究する.特に,組合せ遷移問題の頂点インテグリティに関するパラメータ化計算量の解明は今後の課題である.

    researchmap

  4. 計算機科学アプローチによる組合せ遷移の展開:アルゴリズムの自動生成に向けて

    研究課題/研究課題番号:20H05793  2020年10月 - 2023年3月

    科学研究費助成事業  学術変革領域研究(B)

    伊藤 健洋, 和佐 州洋, 小林 靖明, 大舘 陽太, 山内 由紀子

      詳細を見る

    担当区分:研究分担者  資金種別:競争的資金

    A01班は計算機科学を背景分野とし,組合せ遷移に対するアルゴリズム的メタ定理の構築を目指す.現状,組合せ遷移のアルゴリズム開発は,個々の問題に対する事例研究の度合いが強い.本計画研究では,これら個別に開発されたアルゴリズム手法を「統一された設計技法」へと昇華し,これにより組合せ遷移のアルゴリズムを自動生成できるようにすることを目指す.

  5. 理論的に困難な問題を現実的な時間で解くアルゴリズムとデータ構造の研究

    研究課題/研究課題番号:18H04091  2018年4月 - 2023年3月

    科学研究費助成事業  基盤研究(A)

    上原 隆平, 齋藤 寿樹, 鈴木 顕, 川原 純, 伊藤 健洋, 山中 克久, 吉仲 亮, 大舘 陽太

      詳細を見る

    担当区分:研究分担者  資金種別:競争的資金

    全体では「列挙アルゴリズム」と「遷移問題」と「グラフアルゴリズム」の理論的な研究を進め,これに基づいたBDDによる実装の研究を実施した.個別の研究の進展に留まらず,共同研究の段階に移りつつあると自己評価している.令和元年度は,査読付きジャーナル論文13編,審査付きの国際会議での発表24件と多くの成果を得た.以下に代表的な成果を3つ挙げる.
    1) グラフアルゴリズムと列挙アルゴリズムの両方の技法を併せて,いくつかのグラフクラスに関して効率よく全列挙を行うアルゴリズムを開発し,単なる理論的成果にとどめず,実際にグラフの列挙を実装して実行した.必要に応じてスパコンも利用し,限界に肉薄する計算資源を駆使して,巨大なグラフのカタログを作りWeb上に公開した.
    2) BDD班では,ERATO湊離散構造処理系プロジェクトを皮切りに,近年,盛んに研究が進められている列挙索引化手法であるフロンティア法を拡張した「色付きフロンティア法」を提案した.これを用いて,いくつかのグラフクラスに対する高速な列挙アルゴリズムの開発および実装を行った.これまで高速であるとされてきた列挙アルゴリズム技法である逆探索法では列挙できない大きなインスタンスに対して列挙索引化に成功した.
    3) 隣接互換を基本演算とした最短長ユニバーサル列について,いくつかの理論的な成果を得た.これはデータ圧縮に応用を持つ数学的構造である.
    国際的な共同研究という側面についていえば,本研究グループのメンバー同士の共同研究にとどまらず,国際共著論文という点でも十分な成果をあげたと考えている.例えばカナダの研究グループとの共同研究では,最適化遷移という新しいフレームワークを生み出すことに成功した.これは遷移問題を実社会に応用する上で発生する問題点を解決するものであり,遷移問題を実社会に応用する上で重要なアイデアになると期待されている.
    まず2019年6月に合宿形式の研究会を実施した.そこでそれぞれの研究の進展を発表し,問題意識の共有を図った.そのあとは適宜,国内の研究会や国際会議等を利用して相互に連絡をとりあい,研究を実施した.その結果,別途研究業績にあげた通りの十分な業績をあげることができた.以下,いくつかの具体的な進展をあげる.
    1) 比較的単純なグラフクラスの列挙にも取り組み,単にアルゴリズムを研究開発するだけでなく,実際にスパコンなどに実装し,列挙し,カタログを作ってWeb上に公開した.
    2) 部分グラフに関する遷移問題や,整数計画に関する遷移問題など,いくつもの問題を包括する,より一般的な問題に対する遷移問題に対して,容易性困難性両面からの結果を与えることに成功した.
    3) フロンティア法を拡張した色付きフロンティア法を提案した.フロンティア法の性能はグラフのパス分解の品質と深く関わりを持ち,高品質なグラフのパス分解を求める効率的なアルゴリズムの開発も合わせて必要となる.パス分解アルゴリズムについては,ユトレヒト大学のグループと現在研究・開発を行っており,アルゴリズムの実装および性能の実験的な検証の段階にある.
    4) ZSDD(項分岐決定グラフ)と呼ばれる高圧縮なデータ構造を用いてパスや全域木列挙を行うアルゴリズムを設計した.これは従来のZDD(ゼロサプレス型二分決定グラフ)を用いた手法よりも大幅に記憶量を削減できる.
    上記以外にも,業績の数字には上がっていないが,国際会議のプログラムチェアやプログラムコミッティーなどの運営側に関する実績も数多くある.こうしたソサエティ内での貢献は,理論計算機科学分野での日本の研究の存在感を増すためには重要なロビー活動といえる.こうした社会還元や理論的な進展を含めて,全体的には順調に進んでいると言える.
    令和2年度も合宿形式の研究会を実施して問題意識の共有と,研究の進捗の確認を行いたい.ただ現状はCOVID-19の感染防止の観点から,研究スタイルに工夫が必要である.まずはオンライン型の会議の実施を画策する.そこで予備的に研究打ち合わせなどを行い,ある程度全体の意識共有を計る.事態が収束した頃に合宿形式の研究会を実施したいと考えているが,これは状況によって柔軟に対応することとする.
    列挙アルゴリズムの観点では,パス分解アルゴリズムの性能をあげることが重要である.この性能が上がれば,列挙・索引化アルゴリズムを用いて解ける問題の規模は飛躍的に大きくなると考えられる.パス分解アルゴリズムのさらなる高性能化を行うとともに,それをフロティア法へと適用することにより,実応用への幅を拡張していく.また,グラフの列挙索引化だけでなく,列挙索引化された情報を活用することによる遷移問題に対するアルゴリズムを検討する.また新たに提案したZSDDを用いて,弦グラフなど,より高度なグラフ構造を高速に列挙するアルゴリズムを設計する予定である.
    遷移問題については,理論面での研究は一定の成果が出始めているものの,実社会への応用を考えると,十分に効率的なアルゴリズムとは言えない.これまでの研究で,何が可能で,何が不可能なのかがわかりつつある.これらの結果を基に,パラメタ化アルゴリズムや,近似アルゴリズムなど,様々な観点から研究を進め,実用的なアルゴリズムの開発を目指す.
    また隣接互換による最短長ユニバーサル列については,より詳細な長さの上界を求めることを目指したい.ユニバーサル列は,全ての置換を互換の分解として圧縮表現するデータ構造であり,BDDやZDDと概念的にも似ていることから,今後も重点的に研究する.

  6. 特殊木構造によるFPTアルゴリズム高速化手法の研究

    研究課題/研究課題番号:18K11168  2018年4月 - 2022年3月

    日本学術振興会  科学研究費助成事業  基盤研究(C)

    大舘 陽太

      詳細を見る

    担当区分:研究代表者  資金種別:競争的資金

    配分額:4420000円 ( 直接経費:3400000円 、 間接経費:1020000円 )

    グラフアルゴリズム設計手法の最重要技術の一つである木分解および木幅の利用を推し進め,特殊木構造による固定パラメータ容易 (FPT) アルゴリズム高速化手法の研究を行った.主な成果の例として,以下の問題に対する特殊木構造を用いた高速FPTアルゴリズムを設計した: 部分グラフ同型性判定問題,安全集合問題,グラフ焼却問題,グランディ彩色問題,端点および長さの指定されたパス充填問題,消防士問題,独立集合遷移問題.
    特殊木構造を用いて多くの重要問題のより詳細な計算量を知りたいというのがこの研究課題の動機であったが,結果として種々の問題に対する成果を得ることができ,この手法の有用性を示すことができた.
    従来の手法では木幅と呼ばれる一般性の高い概念を使って問題を解決することが多かったが,それが難しい場合に対しても本課題で扱った特殊木構造を用いれば高速アルゴリズム設計が可能になる場合が分かった.これは,効率的に解ける問題の範囲を広げより詳しくとらえるために重要なステップであり,今後もこの方向での研究を進める必要がある.

    researchmap

  7. グラフ同型性判定問題に対する幅パラメータ固定アルゴリズムの研究

    研究課題/研究課題番号:25730003  2013年4月 - 2016年3月

    日本学術振興会  科学研究費助成事業  若手研究(B)

    大舘 陽太

      詳細を見る

    担当区分:研究代表者  資金種別:競争的資金

    配分額:4160000円 ( 直接経費:3200000円 、 間接経費:960000円 )

    連結木距離幅が定数のグラフに対する同型性判定問題の固定パラメータ容易性を示した.該当論文では,問題そのものを直接解くのではなく,ある種のメタアルゴリズムを作るという方針をとった.グラフ同型性判定の古典的アルゴリズムとして,Weisfeiler-Lehmanアルゴリズムという手法がある.この論文では,このWeisfeiler-Lehmanを一般化・高速化し,ある種のグラフ幅パラメータが定数の場合に対する固定パラメータ容易性を示した.
    関連して,入力グラフがある種の禁止構造を持つ場合を研究した.あるグラフを誘導マイナーとして含まないクラスに対する同型性判定問題に対して計算量二分法を与えた.

    researchmap

  8. 記憶領域制限シナリオにおける計算限界の解明

    研究課題/研究課題番号:24106004  2012年6月 - 2017年3月

    新学術領域研究(研究領域提案型)

    浅野 哲夫

      詳細を見る

    担当区分:研究分担者  資金種別:競争的資金

    配分額:3640000円 ( 直接経費:2800000円 、 間接経費:840000円 )

    本研究では,対数領域計算モデルでの非自明な下界と上界の確立に向けて強力な解析技法の開発を行った.与えられた実数値配列上で,各要素の対して,より大きな値をもつ要素の中で直近のものを見つける直近上位要素発見問題を基本問題として考えた.線形の作業領域を許すと線形時間ですべての直近上位要素を求めることができるが,少ない作業領域でどの程度の高速化が達成できるかが問題である.本研究では,定数個のメモリを用いるだけで十分に高速なアルゴリズムを開発することに成功し,その計算時間とメモリ量との間のトレードオフについても成果を得た.同様の研究結果を計算幾何学やグラフ理論の基本的な問題についても得ることができた.

  9. 省メモリ計算モデル上でのアルゴリズム設計技法の開発

    研究課題/研究課題番号:23300001  2011年4月 - 2015年3月

    基盤研究(B)

    浅野 哲夫

      詳細を見る

    担当区分:研究分担者  資金種別:競争的資金

    配分額:832000円 ( 直接経費:640000円 、 間接経費:192000円 )

    近年の計算機環境は著しい変化を遂げている.計算機の性能が上がるにつれ,より大きな規模の問題が解けるようになり,いわゆるビッグデータ処理が注目を集めているところである.このように問題のサイズは大きくなる一方であるが,データサイズが大きすぎて主記憶に収まりきらないという問題がある.そのために省メモリのアルゴリズムが要求されるが,この分野の研究は始まったばかりである.本研究では,計算幾何学に焦点をあてつつ,グラフ理論の諸問題に対する省メモリアルゴリズム,2値画像処理に対する効率の良いアルゴリズムを開発した.

  10. 混雑度の低い疎なネットワークの設計

    研究課題/研究課題番号:23800004  2011年 - 2012年

    日本学術振興会  科学研究費助成事業  研究活動スタート支援

    大舘 陽太

      詳細を見る

    担当区分:研究代表者  資金種別:競争的資金

    配分額:3250000円 ( 直接経費:2500000円 、 間接経費:750000円 )

    混雑度の低い疎なネットワークの設計問題のうち,特に全域木混雑度問題と呼ばれるグラフに対する最適化問題を研究し,計算理論的に難しい場合と易しい場合に対してある種の線引きを行った.また,1990 年代から注目されている「固定パラメータ計算量」という計算理論的概念も研究し,いくつかの基準に対して困難な場合と容易な場合の2 分法を与えた.研究結果から,この問題は多くの場合で非常に難しいということが分かったので,発見的手法や近似手法などの研究にも取り組み,部分的な成果を得た.

    researchmap

  11. 木幅と関連グラフパラメータの研究

    研究課題/研究課題番号:09J06878  2009年4月 - 2011年3月

    日本学術振興会  科学研究費補助金(特別研究員奨励費)  特別研究員奨励費

    大舘 陽太

      詳細を見る

    担当区分:研究代表者  資金種別:競争的資金

    配分額:1400000円 ( 直接経費:1400000円 )

▼全件表示

 

担当経験のある科目 (本学) 5

  1. 線形代数学Ⅰ

    2020

  2. 線形代数学Ⅱ

    2020

  3. 数理情報学4

    2020

  4. 数理情報学3

    2020

  5. 数理情報学序論2

    2020