論文 - 大舘　陽太

Orientable burning number of graphs. 査読有り

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

Discret. Appl. Math.   367 巻   頁： 116 - 128   2025年5月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.dam.2025.02.004

researchmap

An improved spectral lower bound of treewidth 査読有り

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, Yota Otachi

Information Processing Letters   188 巻   頁： 106536   2025年2月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.ipl.2024.106536

researchmap

Dichotomies for tree minor containment with structural parameters. 査読有り

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

Theoretical Computer Science   1026 巻   頁： 114984   2025年2月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2024.114984

researchmap

Structural parameterizations of vertex integrity. 査読有り

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

Theor. Comput. Sci.   1024 巻   頁： 114954   2025年1月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2024.114954

researchmap

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

Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi

Algorithmica   86 巻 ( 11 ) 頁： 3395 - 3424   2024年11月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00453-024-01261-0

researchmap

Finding Induced Subgraphs from Graphs with Small Mim-Width. 査読有り

Yota Otachi, Akira Suzuki, Yuma Tamura

SWAT     頁： 38 - 16   2024年6月

　詳細を見る

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

DOI： 10.4230/LIPIcs.SWAT.2024.38

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/swat/swat2024.html#OtachiST24

Grouped domination parameterized by vertex cover, twin cover, and beyond. 査読有り

Tesshu Hanaka, Hirotaka Ono, Yota Otachi, Saeki Uda

Theor. Comput. Sci.   996 巻   頁： 114507 - 114507   2024年5月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2024.114507

researchmap

Finding a Reconfiguration Sequence between Longest Increasing Subsequences. 査読有り

Yuuki Aoike, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

IEICE Trans. Inf. Syst.   107 巻 ( 4 ) 頁： 559 - 563   2024年4月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1587/transinf.2023edl8067

researchmap

Structural Parameterizations of Vertex Integrity. 査読有り

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

WALCOM     頁： 406 - 420   2024年3月

　詳細を見る

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

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

researchmap

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

Orientable Burning Number of Graphs. 査読有り

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

WALCOM     頁： 377 - 391   2024年3月

　詳細を見る

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

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

researchmap

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

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

WALCOM     頁： 421 - 435   2024年3月

　詳細を見る

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

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

researchmap

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

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

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

WALCOM     頁： 392 - 405   2024年3月

　詳細を見る

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

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

researchmap

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

Collecting Balls on a Line by Robots with Limited Energy. 査読有り

Tesshu Hanaka, Nicolás Honorato Droguett, Kazuhiro Kurita, Hirotaka Ono, Yota Otachi

IEICE Trans. Inf. Syst.   107 巻 ( 3 ) 頁： 325 - 327   2024年3月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1587/transinf.2023fcl0003

researchmap

On a Spectral Lower Bound of Treewidth. 査読有り

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, Yota Otachi

IEICE Trans. Inf. Syst.   107 巻 ( 3 ) 頁： 328 - 330   2024年3月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1587/transinf.2023fcl0002

researchmap

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

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

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

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

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

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

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

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

Grundy Distinguishes Treewidth from Pathwidth. 査読有り

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

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

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1137/20m1385779

researchmap

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

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

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

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

Parameterized Complexity of Graph Burning. 査読有り

Yasuaki Kobayashi, Yota Otachi

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

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00453-022-00962-8

researchmap

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

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

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

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

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

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

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

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月

　詳細を見る

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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月

　詳細を見る

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

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

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

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

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

Rémy Belmonte, Eun Jung Kim, 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

On bipartite powers of bigraphs 査読有り

Yoshio Okamoto, Yota Otachi, Ryuhei Uehara

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

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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