研究者詳細

顔写真

シユウ　ギヨウ
周　暁
Gyo Shu
所属
大学院情報科学研究科　システム情報科学専攻　知能情報科学講座（アルゴリズム論分野）
職名
教授
学位

  • 博士（情報） （東北大学）

e-Rad 研究者番号
10272022
プロフィール
Graph Theory, Graph Algorithm

学歴 1

  • 東北大学　大学院情報科学研究科　システム情報科学専攻

    1992年4月 ～ 1995年3月

研究分野 1

  • 情報通信 / 情報学基礎論 /

論文 140

  1. The Shortest Path Reconfiguration Problem Based on Relaxation of Reconfiguration Rules

    Naoki Domon, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Lecture Notes in Computer Science　227-241　2024年2月29日

    出版者・発行元： Springer Nature Singapore

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

    ISSN：0302-9743

    eISSN：1611-3349

  2. Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes.

    Toranosuke Kokai, Akira Suzuki 0001, Takahiro Suzuki 0002, Yuma Tamura, Xiao Zhou 0001

    CoRR　abs/2511.22912　2025年11月

    DOI： 10.48550/arXiv.2511.22912 　

  3. Changing induced subgraph isomorphisms under extended reconfiguration rules

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    INFORMATION AND COMPUTATION　307　2025年11月

    DOI： 10.1016/j.ic.2025.105367 　

    ISSN：0890-5401

    eISSN：1090-2651

  4. On the complexity of list 7-I-packing for sparse graph classes

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

    THEORETICAL COMPUTER SCIENCE　1052　2025年10月19日

    DOI： 10.1016/j.tcs.2025.115425 　

    ISSN：0304-3975

    eISSN：1879-2294

  5. Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules.

    Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki 0001, Yuma Tamura, Xiao Zhou 0001

    CoRR　abs/2510.24226　2025年10月

    DOI： 10.48550/arXiv.2510.24226 　

  6. Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules.

    Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki 0001, Yuma Tamura, Xiao Zhou 0001

    ISAAC　39-20　2025年

    DOI： 10.4230/LIPIcs.ISAAC.2025.39 　

  7. Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2025　15411　346-360　2025年

    DOI： 10.1007/978-981-96-2845-2_22 　

    ISSN：0302-9743

    eISSN：1611-3349

  8. 重み付き目標集合選択のパラメータ化計算量

    SUZUKI Takahiro, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2024　(AL-196)　320-331　2024年

    DOI： 10.1007/978-981-97-2340-9_27 　

    ISSN：0304-3975

    eISSN：1879-2294

  9. スパースグラフクラスのためのリストHパッキングの複雑さについて

    GIMA Tatsuya, GIMA Tatsuya, HANAKA Tesshu, KOBAYASHI Yasuaki, OTACHI Yota, SHIRAI Tomohito, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2024　(AL-196)　421-435　2024年

    出版者・発行元： Springer Nature Singapore

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

    ISSN：0302-9743

    eISSN：1611-3349

  10. On the Routing Problems in Graphs with Ordered Forbidden Transitions

    Kota Kumakura, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Lecture Notes in Computer Science　14422 LNCS　359-370　2024年

    出版者・発行元： Springer Nature Switzerland

    DOI： 10.1007/978-3-031-49190-0_26 　

    ISSN：0302-9743

    eISSN：1611-3349

  11. Parameterized complexity of optimizing list vertex-coloring through reconfiguration 査読有り

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM2023)　13973　279-290　2023年3月

    DOI： 10.1007/978-3-031-27051-2_24 　

    ISSN：0302-9743

    eISSN：1611-3349

  12. Decremental optimization of vertex-colouring under the reconfiguration framework

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    International Journal of Computer Mathematics: Computer Systems Theory　8　(1)　80-92　2023年

    DOI： 10.1080/23799927.2023.2185543 　

    ISSN：2379-9927

    eISSN：2379-9935

  13. 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 0001

    CoRR　abs/2312.08639　2023年

    DOI： 10.48550/arXiv.2312.08639 　

  14. 配電損失最小化問題に対する組合せ遷移的アプローチ

    畠山航, 鈴木顕, 伊藤健洋, ZHOU Xiao, 杉村修平, 田邊隆之

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

    ISSN：1883-1893

  15. 区間グラフに対するハミルトン閉路遷移問題

    佐藤颯介, 鈴木顕, 伊藤健洋, ZHOU Xiao

    電子情報通信学会大会講演論文集(CD-ROM)　2021　2021年

    ISSN：1349-144X

  16. 頂点色付け再構成問題に関する最適化バリアント

    YANAGISAWA Yusuke, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2021　(AL-185)　2021年

  17. Decremental Optimization of Vertex-Coloring Under the Reconfiguration Framework

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Lecture Notes in Computer Science　13025 LNCS　(1)　355-366　2021年

    出版者・発行元： Springer International Publishing

    DOI： 10.1007/978-3-030-89543-3_30 　

    ISSN：0302-9743

    eISSN：1611-3349

  18. Approximability of the independent feedback vertex set problem for bipartite graphs

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　849　227-236　2021年

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2020.10.026 　

    ISSN：0304-3975

    eISSN：1611-3349

  19. Minimization and Parameterized Variants of Vertex Partition Problems on Graphs.

    Yuma Tamura, Takehiro Ito, Xiao Zhou 0001

    31st International Symposium on Algorithms and Computation(ISAAC)　181　40-13　2020年

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.ISAAC.2020.40 　

    ISSN：1868-8969

  20. Approximability of the independent feedback vertex set problem for bipartite graphs 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Proceedings of the 14th International Conference and Workshop on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science　12049　286-295　2020年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-39881-1_24 　

    ISSN：0302-9743

    eISSN：1611-3349

  21. The coloring reconfiguration problem on specific graph classes 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    IEICE Trans. on Information and Systems　102-D　(3)　423-429　2019年3月

    出版者・発行元： The Institute of Electronics, Information and Communication Engineers

    DOI： 10.1587/transinf.2018FCP0005 　

    ISSN：0916-8532

    eISSN：1745-1361

  22. グラフ上の経路固定サーバ割当問題のパラメータ複雑性

    岩本裕二, 水田遥河, 鈴木顕, 伊藤健洋, ZHOU Xiao

    情報処理学会全国大会講演論文集　81st　(1)　2019年

  23. グラフ上のパケットルーティング問題のパラメータ複雑性に関する研究

    菊池正太, 鈴木顕, 伊藤健洋, ZHOU Xiao

    情報処理学会全国大会講演論文集　81st　(1)　2019年

  24. 放射状系統作成による配電損失最小化手法と切替手順の算出手法

    杉村修平, 田邊隆之, 鈴木顕, 伊藤健洋, XIAO Zhou

    電気学会研究会資料　(PE-19-079-157/PSE-19-091-169)　2019年

  25. reconfiguration of minimum steiner trees via vertex exchanges 査読有り

    Mizuta, Haruka, Hatanaka, Tatsuhiko, Ito, Takehiro, Zhou, Xiao

    138　79:1-79:11　2019年

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

    DOI： 10.4230/LIPIcs.MFCS.2019.79 　

    ISSN：1868-8969

  26. Parameterized complexity of the list coloring reconfiguration problem with graph parameters 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　739　65-79　2018年8月29日

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2018.05.005 　

    ISSN：0304-3975

  27. グラフの色付きトークン整列問題について (アルゴリズムと計算理論の基礎と応用)

    金野, 駿人, 鈴木, 顕, 山中, 克久, 伊藤, 健洋, 周, 暁

    数理解析研究所講究録　2088　53-62　2018年8月

    出版者・発行元： 京都大学数理解析研究所

    ISSN：1880-2818

  28. 最大2つのエネルギーの閾値回路の計算パワー

    MANIWA Hiroki, OKI Takayuki, SUZUKI Akira, UCHIZAWA Kei, ZHOU Xiao

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)　E101.A　(9)　2018年

    ISSN：1745-1337

  29. 一般化彩色遷移問題に対する線形時間アルゴリズム

    OSAWA Hiroki, SUZUKI Akira, ITO Takehiro, ZHOU Xiao

    電子情報通信学会技術研究報告　118　(356(COMP2018 31-42)(Web))　2018年

    ISSN：0913-5685

  30. Algorithms for Coloring Reconfiguration under Recolorability Constraints 査読有り

    周 暁

    Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), Leibniz International Proceedings in Informatics　123　37:1-37:13　2018年

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

    DOI： 10.4230/LIPIcs.ISAAC.2018.37 　

    ISSN：1868-8969

  31. Computational Power of Threshold Circuits of Energy at most Two. 査読有り

    Hiroki Maniwa, Takayuki Oki, Akira Suzuki, Kei Uchizawa, Xiao Zhou

    IEICE Transactions　101-A　(9)　1431-1439　2018年

    出版者・発行元：

    DOI： 10.1587/transfun.E101.A.1431 　

    ISSN：0916-8508

    eISSN：1745-1337

  32. (リスト)エッジカラーリング再構成問題の複雑さ 査読有り

    OSAWA Hiroki, SUZUKI Akira, ITO Takehiro, ZHOU Xiao

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)　E101A　(1)　232-238　2018年1月1日

    出版者・発行元：

    DOI： 10.1587/transfun.E101.A.232 　

    ISSN：1745-1337 0916-8508

    eISSN：1745-1337

  33. Reconfiguration of Steiner Trees in an Unweighted Graph 査読有り

    Haruka Mizuta, Takehiro Ito, Xiao Zhou

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E100A　(7)　1532-1540　2017年7月

    DOI： 10.1587/transfun.E100.A.1532 　

    ISSN：1745-1337

    eISSN：1745-1337

  34. Color Image Coding Based on Shape-Adaptive All Phase Biorthogonal Transform 査読有り

    Wang Xiaoyan, Wang Chengyou, Zhou Xiao, Yang Zhiqiang

    JOURNAL OF INFORMATION PROCESSING SYSTEMS　13　(1)　114-127　2017年2月

    DOI： 10.3745/JIPS.02.0053 　

    ISSN：1976-913X

  35. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters. 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    CoRR　abs/1705.07551　2017年

  36. The Complexity of (List) Edge-Coloring Reconfiguration Problem 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    WALCOM: Algorithms and Computation　10167　347-358　2017年

    DOI： 10.1007/978-3-319-53925-6_27 　

    ISSN：0302-9743

    eISSN：1611-3349

  37. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters. 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark　83　51:1-51:13　2017年

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

    DOI： 10.4230/LIPIcs.MFCS.2017.51 　

    ISSN：1868-8969

  38. Complexity of Coloring Reconfiguration under Recolorability Constraints. 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand　117　(301(MSS2017 24-46))　62:1-62:12-12　2017年

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

    DOI： 10.4230/LIPIcs.ISAAC.2017.62 　

    ISSN：0913-5685

  39. The coloring reconfiguration problem on specific graph classes 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　10627　152-162　2017年

    出版者・発行元： Springer Verlag

    DOI： 10.1007/978-3-319-71150-8_15 　

    ISSN：1611-3349 0302-9743

    eISSN：1611-3349

  40. The minimum vulnerability problem on specific graph classes 査読有り

    Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

    Journal of Combinatorial Optimization　32　(4)　1288-1304　2016年11月

    DOI： 10.1007/s10878-015-9950-2 　

    ISSN：1382-6905

    eISSN：1573-2886

  41. The multi-service center decision problem is NP-complete for split graphs 査読有り

    Toshimitsu Anzai, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Proceedings of the 2016 International Conference on Applied and Engineering Mathematics (AEM 2016)　2016年10月23日

  42. Reconfiguration of Vertex Covers in a Graph 査読有り

    Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E99D　(3)　598-606　2016年3月

    DOI： 10.1587/transinf.2015FCP0010 　

    ISSN：1745-1361

    eISSN：1745-1361

  43. 汎用彩色再構成の問題のためのアルゴリズム

    OSAWA Hiroki, SUZUKI Akira, SUZUKI Akira, ITO Takehiro, ITO Takehiro, ZHOU Xiao

    情報処理学会研究報告(Web)　2016　(AL-156)　2016年

  44. The Complexity of (List) Edge-Coloring Reconfiguration Problem. 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    CoRR　abs/1609.00109　347-358　2016年

    DOI： 10.1007/978-3-319-53925-6_27 　

    ISSN：0302-9743

    eISSN：1611-3349

  45. Reconfiguration of Steiner Trees in an Unweighted Graph 査読有り

    Haruka Mizuta, Takehiro Ito, Xiao Zhou

    Combinatorial Algorithms　9843　(7)　163-175　2016年

    DOI： 10.1007/978-3-319-44543-4_13 　

    ISSN：0302-9743

    eISSN：1745-1337 1611-3349

  46. Threshold Circuits Detecting Global Patterns in Two-dimensional Maps 査読有り

    Kei Uchizawa, Daiki Yashima, Xiao Zhou

    Journal of Graph Algorithms and Applications　20　(1)　115-131　2016年

    出版者・発行元： Journal of Graph Algorithms and Applications

    DOI： 10.7155/jgaa.00387 　

    ISSN：1526-1719

    eISSN：1526-1719

  47. Algorithms for the Independent Feedback Vertex Set Problem 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E98A　(6)　1179-1188　2015年6月

    DOI： 10.1587/transfun.E98.A.1179 　

    ISSN：1745-1337

  48. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E98A　(6)　1168-1178　2015年6月

    DOI： 10.1587/transfun.E98.A.1168 　

    ISSN：1745-1337

  49. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E98A　(6)　1168-1178　2015年6月

    DOI： 10.1587/transfun.E98.A.1168 　

    ISSN：1745-1337

  50. Experimental evaluations of dynamic algorithm for maintaining shortest-paths trees on real-world networks 査読有り

    Takashi Hasegawa, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Interdisciplinary Information Sciences　21　(1)　25-35　2015年

    出版者・発行元： 東北大学

    DOI： 10.4036/iis.2015.25 　

    ISSN：1340-9050

    eISSN：1347-6157

    詳細を見る 詳細を閉じる

    For a digraph G = (V,A) and a source vertex s ∈ V, suppose that we wish to compute a shortest directed path from s to every vertex v ∈ V \ {s} (if exists) under several arc costs. Frigioni et al. (2000) proposed a dynamic algorithm which efficiently reuses the shortest-paths information computed for the previous arc costs. In this paper, we experimentally evaluate how such a dynamic algorithm works efficiently for real-world networks.

  51. Deterministic Algorithms for the Independent Feedback Vertex Set Problem 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Lecture Notes in Computer Science　8986　351-363　2015年

    DOI： 10.1007/978-3-319-19315-1_31 　

    ISSN：0302-9743

    eISSN：1611-3349

  52. Reconfiguration of Vertex Covers in a Graph 査読有り

    Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

    COMBINATORIAL ALGORITHMS, IWOCA 2014　8986　(3)　164-175　2015年

    DOI： 10.1007/978-3-319-19315-1_15 　

    ISSN：0302-9743

    eISSN：1745-1361 1611-3349

  53. Threshold Circuits for Global Patterns in 2-Dimensional Maps. 査読有り

    Kei Uchizawa, Daiki Yashima, Xiao Zhou

    WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings　306-316　2015年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-319-15612-5_27 　

  54. 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

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

    ISSN：1611-3349 0302-9743

    eISSN：1611-3349

  55. Generalized rainbow connectivity of graphs 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Xiao Zhou

    THEORETICAL COMPUTER SCIENCE　555　35-42　2014年10月

    DOI： 10.1016/j.tcs.2014.01.007 　

    ISSN：0304-3975

    eISSN：1879-2294

  56. Reconfiguration of list L(2,1)-labelings in a graph 査読有り

    Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

    THEORETICAL COMPUTER SCIENCE　544　84-97　2014年8月

    DOI： 10.1016/j.tcs.2014.04.011 　

    ISSN：0304-3975

    eISSN：1879-2294

  57. Bandwidth consecutive multicolorings of graphs 査読有り

    Kazuhide Nishikawa, Takao Nishizeki, Xiao Zhou

    Theoretical Computer Science　532　64-72　2014年5月

    DOI： 10.1016/j.tcs.2013.02.015 　

    ISSN：0304-3975

    eISSN：1879-2294

  58. 有向グラフの最小カタピラ問題について 査読有り

    OKADA Taku, SUZUKI Akira, ITO Takehiro, ZHOU Xiao

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Institute of Electronics, Information and Communication Engineers)　E97A　(3)　848-857　2014年3月

    DOI： 10.1587/transfun.E97.A.848 　

    ISSN：0916-8508

    eISSN：1745-1337

  59. Orthogonal drawings of series-parallel graphs with minimum bends

    Xiao Zhou, Takao Nishizeki

    Proceedings of the 1st Workshop on Algorithms and Computation 2007, WALCOM 2007　3-12　2014年

    出版者・発行元： Bangladesh Academy of Sciences (BAS)

  60. The minimum vulnerability problem on graphs 査読有り

    Yusuke Aoki, Bjarni V Halld´Orsson, Magn´Us M Halld´Orsson, Takehiro Ito, Christian Konrad, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　8881　131-299　2014年

    出版者・発行元： Springer Verlag

    DOI： 10.1007/978-3-319-12691-323 　

    ISSN：1611-3349 0302-9743

  61. Computational Complexity of Competitive Diffusion on (Un)weighted Graphs. 査読有り

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

    CoRR　abs/1412.3334　(AL-154)　2014年

  62. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014)　8881　(6)　314-328　2014年

    DOI： 10.1007/978-3-319-12691-3_24 　

    ISSN：0302-9743

    eISSN：1745-1337 1611-3349

  63. The Minimum Vulnerability Problem on Graphs 査読有り

    Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

    Lecture Notes in Computer Science　8881　299-313　2014年

    DOI： 10.1007/978-3-319-12691-3_23 　

    ISSN：0302-9743

    eISSN：1611-3349

  64. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014)　8881　314-328　2014年

    DOI： 10.1007/978-3-319-12691-3_24 　

    ISSN：0302-9743

  65. On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Algorithmica　67　(2)　161-179　2013年10月

    DOI： 10.1007/s00453-012-9689-4 　

    ISSN：0178-4617

    eISSN：1432-0541

  66. On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

    ALGORITHMICA　67　(2)　161-179　2013年10月

    DOI： 10.1007/s00453-012-9689-4 　

    ISSN：0178-4617

  67. Energy and fan-in of logic circuits computing symmetric Boolean functions 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Theoretical Computer Science　505　74-80　2013年9月

    DOI： 10.1016/j.tcs.2012.11.039 　

    ISSN：0304-3975

    eISSN：1879-2294

  68. Energy-efficient threshold circuits detecting global pattern in 1-dimensional arrays 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Proceedings of the 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　17-17　2013年4月20日

  69. Algorithm for the minimum caterpillar problem with terminals 査読有り

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Proceedings of the 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　2012　(6)　25-25　2013年4月20日

    ISSN：2186-2583

  70. 末端を有する最小カタピラ問題のためのアルゴリズム

    OKADA Taku, SUZUKI Akira, ITO Takehiro, ZHOU Xiao

    情報処理学会研究報告(CD-ROM)　2013　(1)　1-7　2013年2月22日

    ISSN：2186-2583

  71. Generalized Rainbow Connectivity of Graphs 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Xiao Zhou

    Lecture Notes in Computer Science　7748　233-244　2013年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/978-3-642-36065-7_22 　

    ISSN：0302-9743 1611-3349

    eISSN：1611-3349

  72. Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimentional Arrays 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Lecture Notes in Computer Science　7876　248-259　2013年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/978-3-642-38236-9_23 　

    ISSN：1611-3349 0302-9743

    eISSN：1611-3349

  73. On the minimum caterpillar problem in digraphs 査読有り

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7936　729-736　2013年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-642-38768-5_66 　

    ISSN：0302-9743 1611-3349

  74. Complexity of Counting Output Patterns of Logic Circuits. 査読有り

    Kei Uchizawa, Zhenghong Wang, Hiroki Morizumi, Xiao Zhou

    Nineteenth Computing: The Australasian Theory Symposium, CATS 2013, Adelaide, Australia, February 2013　37-43　2013年

    出版者・発行元： Australian Computer Society

  75. ENERGY-EFFICIENT THRESHOLD CIRCUITS COMPUTING MOD FUNCTIONS 査読有り

    AKIRA SUZUKI, KEI UCHIZAWA, XIAO ZHOU

    International Journal of Foundations of Computer Science　24　(1)　15-29　2013年1月

    DOI： 10.1142/S0129054113400029 　

    ISSN：0129-0541

    eISSN：1793-6373

  76. Energy-Efficient Threshold Circuits for Comparison Functions

    UCHIZAWA Kei, ZHOU Xiao

    Interdisciplinary Information Sciences　18　(2)　161-166　2012年12月10日

    出版者・発行元： Graduate School of Information Sciences, Tohoku University

    DOI： 10.4036/iis.2012.161 　

    ISSN：1347-6157

    詳細を見る 詳細を閉じる

    Special Issue on Fundamental Aspects and Recent Developments in Multimedia and VLSI Systems

  77. Small grid drawings of planar graphs with balanced partition 査読有り

    Xiao Zhou, Takashi Hikino, Takao Nishizeki

    Journal of Combinatorial Optimization　24　(2)　99-115　2012年8月

    DOI： 10.1007/s10878-011-9381-7 　

    ISSN：1382-6905

    eISSN：1573-2886

  78. Partitioning a Weighted Tree into Subtrees with Weights in a Given Range 査読有り

    Takehiro Ito, Takao Nishizeki, Michael Schröder, Takeaki Uno, Xiao Zhou

    Algorithmica　62　(3-4)　823-841　2012年4月

    DOI： 10.1007/s00453-010-9485-y 　

    ISSN：0178-4617

    eISSN：1432-0541

  79. An Improved Sufficient Condition Tor Reconfiguration of List Edge-Colorings in a Tree 査読有り

    Takehiro Ito, Kazuto Kawamura, Xiao Zhou

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E95D　(3)　737-745　2012年3月

    DOI： 10.1587/transinf.E95.D.737 　

    ISSN：0916-8532

    eISSN：1745-1361 1611-3349

  80. Algorithms for bandwidth consecutive multicolorings of graphs 査読有り

    Kazuhide Nishikawa, Takao Nishizeki, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7285　117-128　2012年

    DOI： 10.1007/978-3-642-29700-7_11 　

    ISSN：0302-9743 1611-3349

  81. Minimum cost partitions of trees with supply and demand 査読有り

    Takehiro Ito, Takuya Hara, Xiao Zhou, Takao Nishizeki

    Algorithmica　64　(3)　400-415　2012年

    DOI： 10.1007/s00453-011-9573-7 　

  82. Reconfiguration of list L(2, 1)-labelings in a graph 査読有り

    Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

    Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings　544　(1)　34-43　2012年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/978-3-642-35261-4_7 　

    ISSN：0302-9743 0304-3975

    eISSN：1611-3349

    詳細を見る 詳細を閉じる

    For an integer k ≥ 0, suppose that each vertex v of a graph G has a set C(v) ⊆ {0,1, …, k} of labels, called a list of v. A list L(2,1)-labeling of G is an assignment of a label in C(v) to each vertex v of G such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L(2,1)-labeling of a graph into another list L(2,1)-labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L(2,1)-labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k ≥ 6. In contrast, we then show that the problem can be solved in linear time for general graphs if k ≤ 4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L(2,1) -labelings of a tree can be transformed into each other.

  83. Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings 査読有り

    Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E94D　(2)　190-195　2011年2月

    DOI： 10.1587/transinf.E94.D.190 　

    ISSN：1745-1361

  84. Energy-efficient threshold circuits computing Mod functions 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Proceedings of the 17th Computing: the Australasian Theory Symposium (CATS 2011), Conferences in Research and Practice in Information Technology (CRPIT)　119　105-110　2011年1月20日

    出版者・発行元：

  85. グラフの虹接続性に対する困難性およびFPTアルゴリズム

    AOKI Takanori, ITO Takehiro, SUZUKI Akira, UCHIZAWA Kei, ZHOU Xiao

    情報処理学会研究報告(CD-ROM)　2010　(6)　2011年

    ISSN：2186-2583

  86. 次世代断熱発泡剤の研究開発

    田村正則, 関屋章, 徳橋和明, QUAN Hengdao, 水門潤治, 滝澤賢二, CHEN Liang, 高橋明文, 内丸忠文, 鈴木康正, ZHOU Xiaomeng, JIA Xiaoqing

    成形加工(年次大会)　22nd　2011年

  87. Energy and Fan-In of Threshold Circuits Computing Mod Functions 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Lecture Notes in Computer Science　6648　154-163　2011年

    DOI： 10.1007/978-3-642-20877-5_16 　

    ISSN：0302-9743

    eISSN：1611-3349

  88. An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree 査読有り

    Takehiro Ito, Kazuto Kawamura, Xiao Zhou

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011　6648　94-105　2011年

    ISSN：0302-9743

  89. On the rainbow connectivity of graphs: Complexity and FPT algorithms 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings　67　(2)　86-97　2011年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/978-3-642-22685-4_8 　

    ISSN：0302-9743

    eISSN：1611-3349

    詳細を見る 詳細を閉じる

    For a graph G = (V, E) and a color set C, let f : E → C be an edge-coloring of G which is not necessarily proper. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G has a path in which all edges are assigned distinct colors. Chakraborty et al. defined the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. Chen et al. introduced the vertex-coloring version of the problem as a variant, and we introduce the total-coloring version in this paper. We settle the precise computational complexities of all the three problems from two viewpoints, namely, graph diameters and certain graph classes. We also give FPT algorithms for the three problems on general graphs when parameterized by the number of colors in C; these results imply that all the three problems can be solved in polynomial time for any graph with n vertices if |C| = O(log n).

  90. CONVEX DRAWINGS OF INTERNALLY TRICONNECTED PLANE GRAPHS ON O(n2) GRIDS

    XIAO ZHOU, TAKAO NISHIZEKI

    Discrete Mathematics, Algorithms and Applications　2　(3)　347-362　2010年9月1日

    出版者・発行元： World Scientific Pub Co Pte Ltd

    DOI： 10.1142/S179383091000070X 　

    ISSN：1793-8317 1793-8309

    eISSN：1793-8317

  91. Small Grid Drawings of Planar Graphs with Balanced Bipartition 査読有り

    Xiao Zhou, Takashi Hikino, Takao Nishizeki

    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS　5942　47-57　2010年

    ISSN：0302-9743

  92. Minimum cost partitions of trees with supply and demand 査読有り

    Takehiro Ito, Takuya Hara, Xiao Zhou, Takao Nishizeki

    Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II　110　(325)　351-362　2010年

    出版者・発行元： 一般社団法人電子情報通信学会

    DOI： 10.1007/978-3-642-17514-5_30 　

    ISSN：0913-5685

    詳細を見る 詳細を閉じる

    与えられた木Tの各点は供給点または需要点であり,それぞれ供給量または需要量と呼ばれる正整数が割当てられている.Tの各々の需要点vに対し,vの需要量に等しいパワーを,Tの向き付けされた辺を通して,1個の供給点からvに供給したい.Tの各辺eには向きと正整数が割当てられていて,この正整数はTからeを除去するか,あるいはeの向きを逆向きにするのにかかるコストを表している.このとき,Tから辺を除去したり,辺の向きを逆にしたりして,次の条件(a)と(b)を満たすようにTをいくつかの部分木に分割したい.(a)各部分木には,ちょうど1個の供給点があり,その供給量はその部分木に含まれる全ての需要点の需要量の合計以上である.(b)各部分木は供給点を根とした根付き木であり,全ての辺は親から子へ向き付けされている.本論文では,与えられた木Tをこのような根付き部分木に分割するためにかかるコストを最小化する問題を扱う.この最小化問題がNP困難であることを示した上で,この問題を解く擬多項式時間アルゴリズムを与える.更に,この問題に対する多項式時間の完全近似スキーム(FPTAS)も与える.

  93. Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings 査読有り

    Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki

    FRONTIERS IN ALGORITHMICS　6213　274-+　2010年

    DOI： 10.1007/978-3-642-14553-7_26 　

    ISSN：0302-9743

  94. Convex Drawings of Internally Triconnected Plane Graphs on O(n(2)) Grids 査読有り

    Xiao Zhou, Takao Nishizeki

    ALGORITHMS AND COMPUTATION, PROCEEDINGS　5878　760-770　2009年

    ISSN：0302-9743

  95. Partitioning graphs of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Discrete Applied Mathematics　157　(12)　2620-2633　2009年

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.dam.2008.08.012 　

    ISSN：0166-218X

    詳細を見る 詳細を閉じる

    AbstractAssume that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive integer, called a supply or a demand. Each demand vertex can receive “power” from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C has exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in C. If G does not have such a partition, one wishes to partition G into connected components so that each component C either has no supply vertex or has exactly one supply vertex whose supply is no less than the sum of demands in C, and wishes to maximize the sum of demands in all components with supply vertices. We deal with such a maximization problem, which is NP-hard even for trees and strongly NP-hard for general graphs. In this paper, we show that the problem can be solved in pseudo-polynomial time for series–parallel graphs and partial k-trees–that is, graphs with bounded tree-width.

  96. Partitioning a Weighted Tree to Subtrees of Almost Uniform Size 査読有り

    Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (ISAAC2008)　5369　196-207　2008年12月

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/978-3-540-92182-0_20 　

    ISSN：0302-9743

    eISSN：1611-3349

    詳細を見る 詳細を閉じる

    Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are integers such that 0 ≤ l ≤ u. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an "almost uniform" partition is called an (l, u)-partition. We deal with three problems to find an (l, u)-partition of a given graph: the minimum partition problem is to find an (l, u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l, u)-partition with a given number p of components. All these problems are NP-hard even for series-parallel graphs, but are solvable for paths in linear time and for trees in polynomial time. In this paper, we give polynomial-time algorithms to solve the three problems for trees, which are much simpler and faster than the known algorithms.

  97. 木の均一分割問題

    伊藤 健洋, 宇野 毅明, 周 暁, 西関 隆夫

    電子情報通信学会コンピュテーション研究会　55-61　2008年10月

  98. Approximability of partitioning graphs with supply and demand 査読有り

    Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki

    Journal of Discrete Algorithms　6　(4)　627-650　2008年

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.jda.2008.03.002 　

    ISSN：1570-8667

    詳細を見る 詳細を閉じる

    AbstractSuppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive “power” from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless P=NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex.

  99. List total colorings of series-parallel graphs 査読有り

    周 暁, 西関 隆夫

    IEICE Trans.on Fundamentals of Electronics, Communications and Computer Sciences E90-A　E90A　(5)　907-916　2007年5月

    DOI： 10.1093/ietfec/e90-a.5.907 　

    ISSN：0916-8508

    eISSN：1745-1337

  100. Total colorings of degenerate graphs 査読有り

    周 暁, 西関 隆夫

    Combinatorica 27　27　(2)　167-182　2007年3月

    DOI： 10.1007/s00493-007-0050-5 　

    ISSN：0209-9683

  101. Partitioning a multi-weighted graph to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki

    IEICE Transactions　90-D　(2)　449-456　2007年

    出版者・発行元： Institute of Electronics, Information and Communications Engineers (IEICE)

    DOI： 10.1093/ietisy/e90-d.2.449 　

    ISSN：0916-8532

    eISSN：1745-1361

    詳細を見る 詳細を閉じる

    Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers li and ui, 1 ≤ i ≤ q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤ i ≤ q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width.

  102. Algorithms for finding distance-edge-colorings of graphs 査読有り

    Takehiro Ito, Akira Kato, Xiao Zhou, Takao Nishizeki

    Journal of Discrete Algorithms　5　(2)　304-322　2007年

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.jda.2006.03.020 　

    ISSN：1570-8667

    詳細を見る 詳細を閉じる

    For a bounded integer @?, we wish to color all edges of a graph G so that any two edges within distance @? have different colors. Such a coloring is called a distance-edge-coloring or an @?-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.

  103. Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Journal of Discrete Algorithms　4　(1)　142-154　2006年

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.jda.2005.01.005 　

    ISSN：1570-8667

    詳細を見る 詳細を閉じる

    AbstractAssume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph; the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a fixed number p of components. All these problems are NP-complete or NP-hard, respectively, even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u4n) and the p-partition problem can be solved in time O(p2u4n) for any series-parallel graph with n vertices. The algorithms can be extended for partial k-trees, that is, graphs with bounded tree-width.

  104. Partitioning a multi-weighted graph to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki

    Computing and Combinatorics, 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings　63-72　2006年

    DOI： 10.1007/11809678_9 　

  105. Approximability of partitioning graphs with supply and demand 査読有り

    Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki

    Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings　121-130　2006年

    DOI： 10.1007/11940128_14 　

  106. List total colorings of series-parallel graphs 査読有り

    Xiao Zhou, Yuki Matsuo, Takao Nishizeki

    Journal of Discrete Algorithms　3　(1)　47-60　2005年3月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.jda.2003.12.006 　

    ISSN：1570-8667

  107. Orthogonal drawings of series-parallel graphs with minimum bends

    Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　3827　166-175　2005年

    出版者・発行元： Springer Verlag

    DOI： 10.1007/11602613_18 　

    ISSN：1611-3349 0302-9743

  108. Partitioning trees of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    International Journal of Foundations of Computer Science　16　(4)　803-827　2005年

    DOI： 10.1142/S0129054105003303 　

  109. Algorithms for finding distance-edge-colorings of graphs 査読有り

    Takehiro Ito, Akira Kato, Xiao Zhou, Takao Nishizeki

    Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings　798-807　2005年

    DOI： 10.1007/11533719_81 　

  110. Partitioning graphs of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    International Symposium on Circuits and Systems (ISCAS 2005), 23-26 May 2005, Kobe, Japan　160-163　2005年

    DOI： 10.1109/ISCAS.2005.1464549 　

  111. Algorithm for the Cost Edge-Coloring of Trees 査読有り

    Xiao Zhou, Takao Nishizeki

    Journal of Combinatorial Optimization　8　(1)　97-108　2004年3月

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1023/B:JOCO.0000021940.40066.0c 　

    ISSN：1382-6905

    eISSN：1573-2886

  112. Cost Total Colorings of Trees

    Shuji Isobe, Xiao Zhou, Takao Nishizeki

    IEICE Transactions on Information and Systems　E87-D　(2)　337-342　2004年

    出版者・発行元： Institute of Electronics, Information and Communication, Engineers, IEICE

    ISSN：0916-8532

  113. Partitioning a weighted graph to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Graph-Theoretic Concepts in Computer Science, 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers　365-376　2004年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/978-3-540-30559-0_31 　

    詳細を見る 詳細を閉じる

    Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wish to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such an “almost uniform” partition is called an $(l, u) \mbox{-}$partition. We deal with three problems to find an $(l, u) \mbox{-}$partition of a given graph. The minimum partition problem is to find an $(l, u) \mbox{-}$partition with the minimum number of components. The maximum partition problem is defined similarly. The p-partition problem is to find an $(l, u) \mbox{-}$partition with a fixed number p of components. All these problems are NP-complete or NP-hard even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u4n) and the p-partition problem can be solved in time O(p2u4n) for any series-parallel graph of n vertices. The algorithms can be easily extended for partial k-trees, that is, graphs with bounded tree-width.

  114. Multicolorings of Series-Parallel Graphs 査読有り

    Xiao Zhou, Takao Nishizeki

    Algorithmica　38　(2)　271-297　2003年11月

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s00453-003-1060-3 　

    ISSN：0178-4617

    eISSN：1432-0541

  115. List edge-colorings of series-parallel graphs 査読有り

    T Fujino, Zhou, X, T Nishizeki

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E86A　(5)　1034-1045　2003年5月

    ISSN：0916-8508

    eISSN：1745-1337

  116. Linear algorithm for finding list edge-colorings of series-parallel graphs 査読有り

    T Fujino, S Isobe, Zhou, X, T Nishizeki

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E86D　(2)　186-190　2003年2月

    ISSN：0916-8532

  117. List total colorings of series-parallel graphs

    Xiao Zhou, Yuki Matsuo, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　2697　172-181　2003年

    出版者・発行元： Springer Verlag

    DOI： 10.1007/3-540-45071-8_19 　

    ISSN：1611-3349 0302-9743

  118. Algorithms for multicolorings of partial k-trees 査読有り

    Takehiro Ito, Takao Nishizeki, Xiao Zhou

    IEICE Transactions　E86-D　(2)　191-200　2003年

    出版者・発行元：

    ISSN：0916-8532

  119. Algorithms for the multicolorings of partial k-trees 査読有り

    Takehiro Ito, Takao Nishizeki, Xiao Zhou

    Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings　430-439　2002年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/3-540-45655-4_46 　

    詳細を見る 詳細を閉じる

    Let each vertex v of a graph G have a positive integer weight ?(v). Then a multicoloring of G is to assign each vertex v a set of ?(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k. This paper presents an algorithm which finds a multicoloring of any given partial k-tree G with the minimum number of colors. The computation time of the algorithm is bounded by a polynomial in the number of vertices and the maximum weight of vertices in G.

  120. Partitioning trees of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings　612-623　2002年

    DOI： 10.1007/3-540-36136-7_53 　

  121. Algorithm for the cost edge-coloring of trees

    Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　2108　288-297　2001年

    出版者・発行元： Springer Verlag

    DOI： 10.1007/3-540-44679-6_32 　

    ISSN：1611-3349 0302-9743

  122. Total colorings of degenerated graphs

    Shuji Isobe, Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　2076　506-517　2001年

    出版者・発行元： Springer Verlag

    DOI： 10.1007/3-540-48224-5_42 　

    ISSN：1611-3349 0302-9743

  123. Efficient Algorithms for Weighted Colorings of Series-Parallel Graphs 査読有り

    Takao Nishizeki, Xiao Zhou

    2223　514-524　2001年

    DOI： 10.1007/3-540-45678-3_44 　

    ISSN：0302-9743

  124. A Linear Algorithm for Finding \boldmath[{ g,f }]-Colorings of Partial \boldmath{ k }-Trees 査読有り

    Takao Nishizeki, K. Fuse, Xiao Zhou

    Algorithmica　27　(3-4)　227-243　2000年7月

    DOI： 10.1007/s004530010017 　

    ISSN：0178-4617

  125. Algorithms for generalized vertex-rankings of partial k-trees 査読有り

    Takao Nishizeki, Md. Adul Kashem, Xiao Zhou

    Theoretical Computer Science　240　(2)　407-427　2000年6月

    DOI： 10.1016/s0304-3975(99)00240-6 　

    ISSN：0304-3975

  126. Graph coloring algorithms 査読有り

    Zhou, X, T Nishizeki

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E83D　(3)　407-417　2000年3月

    ISSN：0916-8532

  127. Finding Independent Spanning Trees in Partial k-Trees

    Xiao Zhou, Takao Nishizeki

    1969　168-179　2000年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/3-540-40996-3_15 　

    ISSN：1611-3349 0302-9743

  128. Decompositions to Degree-Constrainded Subgraphs Are Simply Reducible to Edge-Colorings 査読有り

    Takao Nishizeki, Xiao Zhou

    Journal of Combinatorial Theory, Series B　75　(2)　270-287　1999年3月

    出版者・発行元： Elsevier BV

    DOI： 10.1006/jctb.1998.1883 　

    ISSN：0095-8956

  129. A Linear Algorithm for Finding Total Colorings of Partial k-Trees 査読有り

    Takao Nishizeki, Xiao Zhou, Shuji Isobe

    1741　347-356　1999年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/3-540-46632-0_35 　

    ISSN：1611-3349 0302-9743

  130. An NC parallel algorithm for generalized vertex-rankings of partial k-trees

    Xiao Zhou, Takao Nishizeki, M.A. Kashem

    Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)　105-111　1997年

    出版者・発行元： IEEE Comput. Soc

    DOI： 10.1109/ISPAN.1997.645078 　

  131. Generalized vertex-rankings of partial k-trees—Extended Abstract

    Xiao Zhou, Takao Nishizeki, Abul Kashem

    1276　212-221　1997年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/bfb0045088 　

    ISSN：1611-3349 0302-9743

  132. An NC parallel algorithm for edge-coloring series-parallel multigraphs

    ZHOU X.

    J. Algorithms　23　359-374　1997年

    DOI： 10.1006/jagm.1996.0830 　

  133. Edge-coloring partial k-trees

    ZHOU X.

    J. Algorithms　21　598-617　1996年

    DOI： 10.1006/jagm.1996.0061 　

  134. A linear algorithm for edge-coloring series-parallel multigraphs

    ZHOU X.

    J. Algorithms　20　(1)　174-201　1996年

    出版者・発行元： Elsevier BV

    DOI： 10.1006/jagm.1996.0008 　

    ISSN：0196-6774

    詳細を見る 詳細を閉じる

    Many combinatorial problems can be efficiently solved for series?parallel multigraphs. However, the edge-coloring problem of finding the minimum number of colors required for edge-coloring given graphs is one of a few well-known combinatorial problems for which no efficient algorithms have been obtained for series?parallel multigraphs. This paper gives a linear algorithm for the problem on series?parallel multigraphs.

  135. OPTIMAL PARALLEL ALGORITHMS FOR EDGE-COLORING PARTIAL K-TREES WITH BOUNDED DEGREES 査読有り

    ZHOU, X, T NISHIZEKI

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E78A　(4)　463-469　1995年4月

    ISSN：0916-8508

    eISSN：1745-1337

  136. Finding optimal edge-rankings of trees

    Xiao Zhou, Takao Nishizeki

    Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms　122-131　1995年1月22日

    出版者・発行元： Association for Computing Machinery

  137. Edge-coloring algorithms 招待有り

    S Nakano, Zhou, X, T Nishizeki

    COMPUTER SCIENCE TODAY　1000　172-183　1995年

    ISSN：0302-9743

  138. Simple reduction of f-colorings to edge-colorings 査読有り

    Takao Nishizeki, Xiao Zhou

    959　223-228　1995年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/BFb0030836 　

    ISSN：1611-3349 0302-9743

  139. A parallel algorithm for edge-coloring partial k-trees

    Takao Nishizeki, Shin-ichi Nakano, Xiao Zhou

    824　359-369　1994年

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/3-540-58218-5_33 　

    ISSN：1611-3349 0302-9743

  140. An efficient algorithm for edge-coloring series parallel multigraphs 査読有り

    Hitoshi Suzuki, Takao Nishizeki, Shin-ichi Nakano, Xiao Zhou

    583　516-529　1992年

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/BFb0023853 　

    ISSN：1611-3349 0302-9743

︎全件表示 ︎最初の5件までを表示

MISC 78

  1. グラフ構造を用いたメンバーシップ支配集合問題の計算複雑性に関する研究

    若山大智, 鈴木顕, 田村祐馬, 周暁

    情報処理学会研究報告(Web)　2025　(AL-203)　2025年

  2. 拡張ルールの下での独立集合および頂点被覆再構成【JST機械翻訳】|||

    HIRAHARA Shuichi, OHSAKA Naoto, SUGA Tatsuhiro, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2025　(AL-203)　2025年

  3. 緩和制約による最短経路再構成

    DOMON Naoki, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2024　(AL-196)　2024年

  4. 重み付きターゲット集合選択のためのアルゴリズム【JST機械翻訳】

    SUZUKI Takahiro, KIMURA Kei, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    電子情報通信学会大会講演論文集(CD-ROM)　2024　2024年

    ISSN： 1349-144X

  5. 遷移ルールの緩和に基づく独立集合遷移問題

    菅達皓, 鈴木顕, 田村祐馬, ZHOU Xiao

    電子情報通信学会大会講演論文集(CD-ROM)　2024　2024年

    ISSN： 1349-144X

  6. Adaptive Popularity Debiasing Aggregator for Graph Collaborative Filtering

    Huachi Zhou, Hao Chen, Junnan Dong, Daochen Zha, Chuang Zhou, Xiao Huang

    Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval　7-17　2023年7月18日

    出版者・発行元： ACM

    DOI： 10.1145/3539618.3591635 　 10.1145/3626772.3657799_references_DOI_NPXFggGzY6RhT3VfeHMmhqzyCbI 　

  7. グラフ構造に基づく順序付き禁則遷移を回避する経路探索の問題について

    KUMAKURA Kota, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2023　(AL-195)　2023年

  8. Regularizing Graph Neural Networks via Consistency-Diversity Graph Augmentations

    Deyu Bo, Binbin Hu, Xiao Wang, Zhiqiang Zhang, Chuan Shi, Jun Zhou

    Proceedings of the AAAI Conference on Artificial Intelligence　36　(4)　3913-3921　2022年6月28日

    出版者・発行元： Association for the Advancement of Artificial Intelligence (AAAI)

    DOI： 10.1609/aaai.v36i4.20307 　 10.1007/s10115-024-02207-2_references_DOI_FDbZcO1VPXsfFTPJPkJ7jkDerbY 　

    ISSN： 2159-5399

    eISSN： 2374-3468

    詳細を見る 詳細を閉じる

    <jats:p>Despite the remarkable performance of graph neural networks (GNNs) in semi-supervised learning, it is criticized for not making full use of unlabeled data and suffering from over-fitting. Recently, graph data augmentation, used to improve both accuracy and generalization of GNNs, has received considerable attentions. However, one fundamental question is how to evaluate the quality of graph augmentations in principle? In this paper, we propose two metrics, Consistency and Diversity, from the aspects of augmentation correctness and generalization. Moreover, we discover that existing augmentations fall into a dilemma between these two metrics. Can we find a graph augmentation satisfying both consistency and diversity? A well-informed answer can help us understand the mechanism behind graph augmentation and improve the performance of GNNs. To tackle this challenge, we analyze two representative semi-supervised learning algorithms: label propagation (LP) and consistency regularization (CR). We find that LP utilizes the prior knowledge of graphs to improve consistency and CR adopts variable augmentations to promote diversity. Based on this discovery, we treat neighbors as augmentations to capture the prior knowledge embodying homophily assumption, which promises a high consistency of augmentations. To further promote diversity, we randomly replace the immediate neighbors of each node with its remote neighbors. After that, a neighbor-constrained regularization is proposed to enforce the predictions of the augmented neighbors to be consistent with each other. Extensive experiments on five real-world graphs validate the superiority of our method in improving the accuracy and generalization of GNNs.</jats:p>

  9. 放射状系統作成による配電損失最小化手法と切替手順の算出手法—Method for Distribution Loss Minimization and Switching Operation Procedures with Radial Network Reconfiguration—電力技術 電力系統技術合同研究会 (1)電力技術・電力系統技術一般,(2)分散電源・次世代グリッド

    杉村 修平, 田邊 隆之, 鈴木 顕, 伊藤 健洋, 周 暁

    電気学会研究会資料. PSE = The papers of Technical Meeting on "Power Systems Engineering", IEE Japan / 電力系統技術研究会 [編]　2019　(91-103・156・158-169)　25-29　2019年9月

    出版者・発行元： 東京 : 電気学会

  10. Erratum: On Random Walk Based Weighted Graph Sampling [IEICE Transactions on Information and Systems Vol.E101.D (2018) , No.2 pp.535-538]

    ZHOU Jiajun, LIU Bo, DENG Lu, CHEN Yaofeng, XIAO Zhefeng

    IEICE Transactions on Information and Systems　E101.D　(7)　1980_e1-1980_e1　2018年7月1日

    出版者・発行元： The Institute of Electronics, Information and Communication Engineers

    DOI： 10.1587/transinf.2018ede0006 　

    ISSN： 0916-8532

    eISSN： 1745-1361

  11. Drug Similarity Integration Through Attentive Multi-view Graph Auto-Encoders

    Tengfei Ma, Cao Xiao, Jiayu Zhou, Fei Wang

    Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence　3477-3483　2018年7月

    出版者・発行元： International Joint Conferences on Artificial Intelligence Organization

    DOI： 10.24963/ijcai.2018/483 　 10.1109/bibm52615.2021.9669707_references_DOI_SK5DIk6p1EpXYH81RBroAs3rPjd 　

    詳細を見る 詳細を閉じる

    <jats:p>Drug similarity has been studied to support downstream clinical tasks such as inferring novel properties of drugs (e.g. side effects, indications, interactions) from known properties. The growing availability of new types of drug features brings the opportunity of learning a more comprehensive and accurate drug similarity that represents the full spectrum of underlying drug relations. However, it is challenging to integrate these heterogeneous, noisy, nonlinear-related  information to learn accurate similarity measures especially when labels are scarce. Moreover, there is a trade-off between accuracy and interpretability. In this paper, we propose to learn accurate and interpretable similarity measures from multiple types of drug features. In particular, we model the integration using multi-view graph auto-encoders, and add attentive mechanism to determine the weights for each view with respect to corresponding tasks and features for better interpretability. Our model has flexible design for both semi-supervised and unsupervised settings. Experimental results demonstrated significant predictive accuracy improvement. Case studies also showed better model capacity (e.g. embed node features) and interpretability.</jats:p>

  12. The Coloring Reconfiguration Problem on Specific Graph Classes (システム数理と応用)

    HATANAKA TATSUHIKO, ITO TAKEHIRO, ZHOU XIAO

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　117　(301)　23-27　2017年11月16日

    出版者・発行元： 電子情報通信学会

    ISSN： 0913-5685

  13. Energy-efficient Threshold Circuits Computing Generalized Symmetric Functions (理論計算機科学の最先端)

    Maniwa Hiroki, Oki Takayuki, Suzuki Akira, Uchizawa Kei, Zhou Xiao

    数理解析研究所講究録　2040　(2040)　21-26　2017年7月

    出版者・発行元： 京都大学数理解析研究所

    ISSN： 1880-2818

  14. Reachability between Steiner Trees in a Graph (コンピュテーション)

    MIZUTA HARUKA, ITO TAKEHIRO, ZHOU XIAO

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　116　(116)　109-113　2016年6月24日

    出版者・発行元： 電子情報通信学会

    ISSN： 0913-5685

  15. DS-1-5 A Fixed-Parameter Algorithm for the List Coloring Reconfiguration Problem

    Hatanaka Tatsuhiko, Ito Takehiro, Zhou Xiao

    電子情報通信学会総合大会講演論文集　2016　(1)　"S-8"-"S-9"　2016年3月1日

    出版者・発行元： 一般社団法人電子情報通信学会

  16. Algorithms for the Independent Feedback Vertex Set Problem

    TAMURA Yuma, ITO Takehiro, ZHOU Xiao

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　E98.A　(6)　1179-1188　2015年

    出版者・発行元： The Institute of Electronics, Information and Communication Engineers

    DOI： 10.1587/transfun.e98.a.1179 　 10.1016/j.tcs.2020.10.026_references_DOI_PB8WLr9A28KbVArvKU2Rzov8IEh 　 10.1007/978-3-030-39881-1_24_references_DOI_PB8WLr9A28KbVArvKU2Rzov8IEh 　

    ISSN： 0916-8508

    eISSN： 1745-1337

    詳細を見る 詳細を閉じる

    A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

  17. グラフのリスト点彩色の遷移

    畑中 達彦, 伊藤 健洋, 周 暁

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　114　(238)　19-24　2014年10月8日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    グラフの各点には,その点に割り当てることができる色のリストが与えられているとする.本稿では,1つのリスト点彩色から同じグラフの別のリスト点彩色へ,段階的に遷移できるかどうか判定する問題を扱う.ただし,一度にはただ1点の色のみ変更することができ,遷移の過程でも常にリスト点彩色でなければならない.この問題は平面2部グラフにおいてPSPACE完全であることが知られている.本稿では,この問題をグラフのパス幅の観点から解析する.はじめに,この問題はパス幅2のグラフでさえPSPACE完全であることを示す.一方で,パス幅1のグラフに対しては,多項式時間で解けることを示す.

  18. グラフの脆弱性最小化問題

    青木 悠輔, Halldorsson Bjarni V., Halldorsson Magnus M., 伊藤 健洋, KONRAD Christian, 周 暁

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　114　(238)　9-15　2014年10月8日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    無向グラフGの各辺eには,コストcost(e),しきい値vul(e),容量cap(e)と呼ばれる3つの非負整数が与えられているとする.本稿で扱う脆弱性最小化問題とは,正整数kとGの2つの点が与えられたとき,コストの和が最小になるように,与えられた2点を結ぶk本の道を見つける問題である.ただし,各辺eは,vul(e)本以下の辺共有であれば一切のコストを支払うことなく共有でき,コストcost(e)を支払えば辺eの容量cap(e)本まで共有できる.脆弱性最小化問題は,無向グラフにおける辺素パス問題や共通辺最小化問題,辺コストフロー最小化問題などの一般化であり,NP困難であると知られている.本稿では,グラフクラスの観点から脆弱性最小化問題を解析する.はじめに,しきい値グラフや直並列二部グラフに対してさえ,この問題がNP困難であることを示す.一方で,木幅制限グラフに対しては,この問題が擬多項式時間で解けることを示す.最後に,弦グラフに対しては,道の本数んをパラメータとしたFPTアルゴリズムを与える.

  19. The Independent Feedback Vertex Set Problem (コンピュテーション)

    田村 祐馬, 伊藤 健洋, 周 暁

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　114　(80)　13-18　2014年6月13日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    無向グラフGのフィードバック点集合Fとは,GからFを取り除くと,残されたグラフが林になるようなGの点部分集合のことである.また,FがGの独立点集合をなすとき,Fはフィードバック独立点集合という.本稿では,与えられたグラフに対し,点数が最小のフィードバック独立点集合を求める問題について研究する.この問題は,平面的二部グラフに対してさえNP困難であることが示せるため,我々はいくつかの特別なグラフクラスに着目する.まず我々は,この問題が木幅制限グラフと弦グラフに対して線形時間で解けることを示す.次に,平面グラフに対しては,解のサイズをパラメータとしたFPTアルゴリズムを与える.

  20. フィードバック独立点集合問題

    田村 祐馬, 伊藤 健洋, 周 暁

    研究報告アルゴリズム（AL）　2014　(3)　1-6　2014年6月6日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    無向グラフ G のフィードバック点集合 Ｆ とは，G から F を取り除くと，残されたグラフが林になるような G の点部分集合のことである．また，Ｆ が G の独立点集合をなすとき，Ｆ はフィードバック独立点集合という．本稿では，与えられたグラフに対し，点数が最小のフィードバック独立点集合を求める問題について研究する．この問題は，平面的二部グラフに対してさえ NP 困難であることが示せるため，我々はいくつかの特別なグラフクラスに着目する．まず我々は，この問題が木幅制限グラフと弦グラフに対して線形時間で解けることを示す．次に，平面グラフに対しては，解のサイズをパラメータとした FPT アルゴリズムを与える．A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices. This problem is NP-hard even for planar bipartite graphs, and hence we focus on some special classes of graphs. We first show that the problem is solvable in linear time for bounded treewidth graphs and chordal graphs. Then, we give an FPT algorithm for planar graphs when parameterized by the solution size.

  21. グラフの経路固定サーバ割当問題に関する研究 (計算理論とアルゴリズムの新潮流)

    大日野 肇, 伊藤 健洋, 鈴木 顕, 内澤 啓, 周 暁

    数理解析研究所講究録　1894　41-44　2014年5月

    出版者・発行元： 京都大学

    ISSN： 1880-2818

  22. Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimensional Arrays (New Trends in Theoretical Computer Science)

    鈴木 顕, 内澤 啓, 周 暁

    数理解析研究所講究録　1849　133-134　2013年8月

    出版者・発行元： 京都大学

    ISSN： 1880-2818

  23. 関数$P^n_D$を計算するしきい値回路 (理論計算機科学の新展開)

    八島 大樹, 内澤 啓, 周 暁

    数理解析研究所講究録　1849　127-132　2013年8月

    出版者・発行元： 京都大学

    ISSN： 1880-2818

  24. 論理回路の出力パターン数え上げ

    内澤 啓, 王 征泓, 森住 大樹, 周 暁

    研究報告アルゴリズム（AL）　2013　(15)　1-6　2013年5月10日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0369-5123

    詳細を見る 詳細を閉じる

    s個の論理素子g1,g2,...,gsからなる論理回路をCとする．この時，入力x∈{0,1}nに対するCの出力パターンを，(g1(x),g2(x),...,gs(x))∈{0,1}sなる長さsのベクトルと定義する．但し，1<=i<=sなるiについて，gi(x)はxに対する素子giの出力とする．ここで，任意の2入力ブール関数f:{0,1}2→{0,1}について，回路を構成する素子の全てが関数fを計算する論理回路をf-回路と定義する．本論文では，入力としてf-回路C が与えられた時に，Cの出力パターンを数え上げる問題に着目し，その計算複雑さの解析を行った．その結果，この問題がfによって，多項式時間で計算可能となるか，又は#P完全のいずれかになることを明らかにした．即ち，fに関する二分定理を得た．Let C be a logic circuit consisting of s gates g1,g2,...,gs, then the output pattern of C for an input x∈{0,1}n is defined to be a vector (g1(x),g2(x),...,gs(x))∈{0,1}s of the outputs of g1, g2,...,gs for x. For each f : {0,1}2 → {0,1}, we define an f-circuit as a logic circuit where every gate computes f, and investigate computational complexity of the following counting problem: Given an f-circuit C, how many output patterns arise in C? We then provide a dichotomy result on the counting problem: We prove that the problem is solvable in polynomial time if f is PARITY or any degenerate function, while the problem is #P-complete even for constant-depth f-circuits if f is one of the other functions, such as AND, OR, NAND and NOR.

  25. Reconfiguration of List L(2,1)-Labelings in a Graph (コンピュテーション)

    伊藤 健洋, 川村 一斗, 小野 廣隆, 周 暁

    電子情報通信学会技術研究報告 : 信学技報　112　(340)　33-40　2012年12月10日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    あらまし非負整数κ≧0に対し,グラフGの各点νには,ラベルの集合0(ν)⊆{0,1,...,κ}が与えられているとする.このとき,σのリストL(2,1)ラベリングとは,σの各点勿に0@)に含まれるラベルを1つ割り当てることをいう.ただし,隣接する任意の2点には少なくとも2離れたラベルを割り当て,距離2にある任意の2点には少なくとも1離れたラベルを割り当てなければならない.本論文では,グラフGのリストL(2,1)ラベリングが2つ与えられたとき,一方のラベル割当から他方のラベル割当へ段階的に遷移させたい.ただし,1回に変更できるのは1点のラベル割当のみであり,こうして得られるラベル割当もやはりGのリストL(2,1)ラベリングでなければならない.本論文では,κ≧6のとき,この問題は平面二部グラフに対してPSPACE完全であることを証明する.一方で,κ≦4のときには,この問題が任意のグラフに対して線形時間で解けることを示す.さらに,グラフを木に限定したとき,任音の2つのリストL(2.1、ラベリングが互いに遷移できるための十分条件を与える.

  26. Algorithms for Bandwidth Consecutive Multicolorings of Graphs (コンピュテーション)

    西川 和秀, 西関 隆夫, 周 暁

    電子情報通信学会技術研究報告 : 信学技報　111　(360)　17-24　2011年12月16日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    単純グラフGの各点vには正整数重みb(v)が,各辺(v,w)には非負整数重みb(v,w)が付いているとき,Gの帯域幅連続多重彩色とは,Gの各点vに連続したb(v)個の正整数(色)を割り当てることである.ただし,各辺(v,w)について,点vに割り当てられた色と点wに割り当てられた色はb(v,w)+1以上離れていなければならない.点に割り当てられた最大の整数はその彩色のスパンと呼ばれる.本文では,まずこのような彩色の基本的な性質を調べる.次に,直並列グラフGの帯域幅連続多重彩色でスパンが最小なものを求める問題に対して,擬多項式時間厳密アルゴリズムおよび完全多項式時間近似スキームを与える.最後に,これらの結果を部分k-木,即ち,木幅が定数であるグラフに拡張する.

  27. 木,カクタスにおける点被覆の遷移可能性 (コンピュテーション)

    野岡 弘幸, 伊藤 健洋, 周 暁

    電子情報通信学会技術研究報告 : 信学技報　111　(360)　25-32　2011年12月16日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    本文では,グラフGの点被覆が2つ与えられたとき,その一方から他方へGの点被覆のみを経由して,段階的に遷移する事ができるか判定する問題を扱う.ただし,遷移の過程に現れるGの点被覆は,そのサイズが与えられた整数k以下でなければならなく,一つ前の点被覆からちょうど1点を付け加えるか取り除くことで得られなければならない.この判定問題は,平面グラフに対してPSPACE完全である事が知られている.本文では,グラフをカクタスに制限したとき,どの点被覆の組でも常に遷移できるためのkに関する十分条件を与える.また,木に対しては,与えられた2つの点被覆が遷移できるための最小のkを計算する線形時間アルゴリズムを与える.

  28. 木のリスト辺彩色の遷移可能性

    川村 一斗, 伊藤 健洋, 周 暁

    電子情報通信学会技術研究報告. COMP, コンピュテーション　110　(464)　53-60　2011年3月2日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    本論文では,同じグラフのリスト辺彩色が2つ与えられたとき,一方の彩色から他方の彩色へ段階的に遷移させたい.ただし,1回に変更(再彩色)できるのは1本の辺の色のみであり,遷移の途中で得られる彩色は全てリスト辺彩色でなければならない.従来,木に対し,任意のリスト辺彩色が互いに遷移できるための十分条件が知られていた.本論文では,木に対し,従来の十分条件を改良した新しい十分条件を与える.我々の十分条件は,ある意味で最良である.証明は構成的であり,与えられたリスト辺彩色を実際に遷移させる多項式時間アルゴリズムが得られる.木の点数をnとすると,アルゴリズムはO(n^2)回の再彩色を行う遷移を見つける.我々の十分条件を満たす長さnの道でΩ(n^2)回の再彩色を必要とする問題例があるため,この再彩色回数の上界はタイトである.

  29. DS-1-4 剰余関数を計算するしきい値回路のエネルギー複雑度とファンイン(DS-1.COMP学生シンポジウム,シンポジウムセッション)

    鈴木 顕, 内澤 啓, 周 暁

    電子情報通信学会総合大会講演論文集　2011　(1)　"S-7"-"S-8"　2011年2月28日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 1349-1369

    詳細を見る 詳細を閉じる

    We consider a threshold circuit C computing the modulus function MOD_m, and investigate a relationship between energy e and fan-in l of C, where the energy e is defined to be the maximum number of gates outputting "1" over all inputs to C, and the fan-in l to be the maximum number of inputs of every gate in C. We first prove that MOD_m of n variables can be computed by a threshold circuit of energy e=O(n/l) and fan-in l, and then show that the upper bound on the energy e is almost tight by providing a lower bound e=Ω((n-m)/l). Our results imply that there exists a tradeoff between the energy and fan-in of threshold circuits computing the modulus function.

  30. Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs (アルゴリズム(AL) Vol.2011-AL-134)

    Takanori Aoki, Takehiro Ito, Akira Suzuki, Kei Uchizawa, Xiao Zhou

    研究報告アルゴリズム（AL）　2011　(4)　1-8　2011年2月28日

    出版者・発行元： 情報処理学会

    ISSN： 2186-2583

    詳細を見る 詳細を閉じる

    For a graph G = (V,E) and a color set C, let f : E → C be an edge-coloring of G which is not necessarily proper. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G has a path in which all edges are assigned distinct colors by f. In this paper, we give three results for the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. The first is to show that the problem is strongly NP-complete even for outerplanar graphs. We also show that the problem is strongly NP-complete for graphs of diameter 2. In contrast, as the second result, we show that the problem can be solved in polynomial time for cacti. Notice that both outerplanar graphs and cacti are of treewidth 2, and hence our complexity analysis is precise in some sense. The third is to give an FPT algorithm for general graphs when parameterized by the number of colors in C; this result implies that the problem can be solved in polynomial time for general graphs with n vertices if |C| = O(log n).For a graph G = (V,E) and a color set C, let f : E → C be an edge-coloring of G which is not necessarily proper. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G has a path in which all edges are assigned distinct colors by f. In this paper, we give three results for the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. The first is to show that the problem is strongly NP-complete even for outerplanar graphs. We also show that the problem is strongly NP-complete for graphs of diameter 2. In contrast, as the second result, we show that the problem can be solved in polynomial time for cacti. Notice that both outerplanar graphs and cacti are of treewidth 2, and hence our complexity analysis is precise in some sense. The third is to give an FPT algorithm for general graphs when parameterized by the number of colors in C; this result implies that the problem can be solved in polynomial time for general graphs with n vertices if |C| = O(log n).

  31. Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings

    ITO Takehiro, SAKAMOTO Naoki, ZHOU Xiao, NISHIZEKI Takao

    IEICE Transactions on Information and Systems　E94-D　(2)　190-195　2011年

    出版者・発行元： The Institute of Electronics, Information and Communication Engineers

    DOI： 10.1587/transinf.e94.d.190 　 10.1007/978-3-642-14553-7_26 　

    ISSN： 0916-8532

    eISSN： 1745-1361

    詳細を見る 詳細を閉じる

    Let C be a set of colors, and let ω(c) be an integer cost assigned to a color c in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors in C. The cost ω(ƒ) of an edge-coloring ƒ of G is the sum of costs ω(ƒ(e)) of colors ƒ(e) assigned to all edges e in G. An edge-coloring ƒ of G is optimal if ω(ƒ) is minimum among all edge-colorings of G. In this paper, we show that the problem of finding an optimal edge-coloring of a tree T can be simply reduced in polynomial time to the minimum weight perfect matching problem for a new bipartite graph constructed from T. The reduction immediately yields an efficient simple algorithm to find an optimal edge-coloring of T in time O(n1.5Δlog (nNω)), where n is the number of vertices in T, Δ is the maximum degree of T, and Nω is the maximum absolute cost |ω(c)| of colors c in C. We then show that our result can be extended for multitrees.

  32. 剰余関数を計算するエネルギー複雑度の小さいしきい値回路

    鈴木 顕, 内沢 啓, 周 暁

    電子情報通信学会技術研究報告. COMP, コンピュテーション　110　(325)　7-13　2010年11月26日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    本論文では,任意の整数e≧2について,n入力MOD_m関数が素子数s=O(e(n/m)^<1/(e-1)>)かつエネルギー複雑度eなるしきい値回路Cで計算できることを示す.ここで,eは"1"を出力する素子の最大数である,すなわち,Cは任意の入力に対して高々e個の素子しか"1"を出力しない.本論文で得られた素子数の上界は,これまで知られていた下界s=Ω(e(n/m)^<1/e>)とほぼ一致する.

  33. 木の最小コスト辺彩色のマッチングへの帰着

    伊藤 健洋, 坂本 直樹, 周 暁, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　110　(214)　9-15　2010年9月22日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    色集合をCで表し,各色c∈Cに割当てられた整数コストをω(c)で表す.グラフGの辺彩色とは,任意の隣接する2辺が異なる色になるように,Gの各辺にCに含まれる色を割当てることである.Gの辺彩色fのコストω(f)とは,Gの全ての辺eに割当てられた色f(e)のコストω(f(e))の合計と定義する.Gの全ての辺彩色のうち,コストが最小である辺彩色を最適な辺彩色と呼ぶ.本論文では,木Tの最適な辺彩色を求める問題が,Tから新たに構成された二部グラフの最小重み完全マッチング問題に多項式時間で帰着できることを示す.この帰着から,Tの最適な辺彩色をO(n^<1.5>Δlog(nN_ω))時間で求める単純なアルゴリズムが直ちに得られる.ここで,nはTの点数であり,ΔはTの最大次数であり,N_ωは色c∈Cのコストのうち最も大きな絶対値|ω(c)|である.本論文では,この帰着が多重木にも拡張できることを示す.

  34. バランスのよいグラフ分割を用いた平面グラフの小面積格子描画法

    周 暁, 引野 高嗣, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　109　(235)　9-15　2009年10月9日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    平面グラフGの格子描画では,Gの各点は2次元整数格子上に配置され,各辺は直線分として描かれ,どの2辺も共通の端点以外では交差しない.任意の平面グラフGは(n-2)×(n-2)の整数格子上に格子描画を持ち,それは線形時間で求まる.ここで,nはGの点数である.本文では,平面グラフGがバランスよい二分割を持つならば,Gは小さな格子描画を持つことを示す.より詳細に言えば,分離点対がGを二つの辺素な部分グラフG_1とG_2に二分割するならば,GはW×Hの格子描画を持つ.ここで,幅Wと高さHはともにG_1とG_2の点数が多い方の数より小さい.特に,任意の直並列グラフは(2n/3)×(2n/3)の格子描画を持ち,それは線形時間で求まる.

  35. Degree distributions of the visibility graphs mapped from fractional Brownian motions and multifractal random walks

    Xiao-Hui Ni, Zhi-Qiang Jiang, Wei-Xing Zhou

    Physics Letters A　373　(42)　3822-3826　2009年10月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.physleta.2009.08.041 　 10.1143/jpsj.80.074001_references_DOI_VDMSV7zCTbGr9CgU5kMP47IlL9N 　

    ISSN： 0375-9601

  36. A-026 グラフ分割を用いた格子描画法(モデル・アルゴリズム・プログラミング,一般論文)

    引野 高嗣, 周 暁, 西関 隆夫

    情報科学技術フォーラム講演論文集　8　(1)　309-310　2009年8月20日

    出版者・発行元： FIT(電子情報通信学会・情報処理学会)運営委員会

  37. A-027 Convex Drawings of Internally Triconnected Plane Graphs on O(n^2) Grids

    Zhou Xiao, Nishizeki Takao

    情報科学技術フォーラム講演論文集　8　(1)　311-312　2009年8月20日

    出版者・発行元： FIT(電子情報通信学会・情報処理学会)運営委員会

    詳細を見る 詳細を閉じる

    In a convex grid drawing of a plane graph, every edge is drawn as a straight-line segment without any edge-intersection, every vertex is located at a grid point, and every facial cycle is drawn as a convex polygon. A plane graph G has a convex drawing if and only if G is internally triconnected. It has been known that an internally triconnected plane graph G of n vertices has a convex grid drawing on a grid of O(n^3) area if the triconnected component decomposition tree of G has at most four leaves. In this paper, we improve the area bound O(n^3) to O(n^2), which is optimal within a coefficient. More precisely, we show that G has a convex grid drawing on a 2n×4n grid. We also present an algorithm to find such a drawing in linear time.

  38. Convex Drawings of Internally Triconnected Plane Graphs on O (n²) Grids

    2009年度　(2)　1-8　2009年8月

    ISSN： 1884-0930

  39. Convex Drawings of Internally Triconnected Plane Graphs on O (n²) Grids (アルゴリズム(AL) Vol.2009-AL-125)

    Xiao Zhou, Takao Nishizeki

    研究報告アルゴリズム（AL）　2009　(2)　1-8　2009年7月14日

    出版者・発行元： 情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    In a convex grid drawing of a plane graph, every edge is drawn as a straight-line segment without any edge-intersection, every vertex is located at a grid point, and every facial cycle is drawn as a convex polygon. A plane graph G has a convex drawing if and only if G is internally triconnected. It has been known that an internally triconnected plane graph G of n vertices has a convex grid drawing on a grid of O (n3) area if the triconnected component decomposition tree of G has at most four leaves. In this paper, we improve the area bound O(n3) to O(n2), which is optimal within a coefficient. More precisely, we show that G has a convex grid drawing on a 2n x 4n grid. We also present an algorithm to find such a drawing in linear time.In a convex grid drawing of a plane graph, every edge is drawn as a straight-line segment without any edge-intersection, every vertex is located at a grid point, and every facial cycle is drawn as a convex polygon. A plane graph G has a convex drawing if and only if G is internally triconnected. It has been known that an internally triconnected plane graph G of n vertices has a convex grid drawing on a grid of O (n3) area if the triconnected component decomposition tree of G has at most four leaves. In this paper, we improve the area bound O(n3) to O(n2), which is optimal within a coefficient. More precisely, we show that G has a convex grid drawing on a 2n x 4n grid. We also present an algorithm to find such a drawing in linear time.

  40. 3連結平面グラフの細分の格子凸描画

    周 暁, 阿部 崇, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　108　(237)　77-84　2008年10月3日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    グラフGの格子凸描画では,各辺が互いに交差しないように直線分で描画され,各点が整数座標を持ち,Gの全ての面が凸多角形である.n個の点からなる3連結平面グラフは面積(n-1)×(n-1)の格子へ凸描画できることが知られている.次数2の点がある平面グラフGは3連結ではないが,格子凸描画を持つ場合もある.しかし,面積がO(n^2)とは限られない.本論文では,平面グラフGが3連結平面グラフの細分であるとき,即ち3連結平面グラフの辺に次数2の点を挿入してGが得られるとき,Gの格子凸描画で面積がO(n^3)であるものを求める線形時間アルゴリズムを与える.

  41. Orthogonal drawings of series-parallel graphs with minimum bends

    ZHOU Xiao, NISHIZEKI Takao

    SIAM J. Discrete Math.　22　(4)　1570-1604　2008年

    出版者・発行元： Society for Industrial and Applied Mathematics

    DOI： 10.1137/060667621 　

    ISSN： 0895-4801

    eISSN： 1095-7146

  42. 直並列グラフの折れ曲がり最小の直交描画

    周 暁, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　105　(343)　7-14　2005年10月18日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    グラフの平面描画で各辺が水平線分と垂直線分からなる折れ線として描画されているものは, 直交描画と呼ばれる.直交描画の辺の描画の中の水平線分と垂直線分の交点は折れ曲がりと呼ばれる.本論文では, 最大次数が3以下の直並列グラフGが与えられたときに, Gの直交描画で折れ曲がりの個数が最小なものを線形時間で見つけるアルゴリズムを与える.このアルゴリズムは既知のアルゴリズムより高速であり, しかも簡単である.またGの直交描画の折れ曲がりの個数に関する最良の上界も与える.

  43. Optimal parallel algorithm for edge-coloring partial k-trees with bounded degrees

    Takao Nishizeki, Xiao Zhou

    Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN)　167-174　2002年12月17日

    出版者・発行元： IEEE Comput. Soc. Press

    DOI： 10.1109/ispan.1994.367150 　

    詳細を見る 詳細を閉じる

    Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by k). The edge-coloring problem is one of the well-known combinatorial problems for which no NC algorithms have been obtained for partial k-trees. This paper gives an optimal and first NC parallel algorithm to find an edge-coloring of any given partial k-tree using a minimum number of colors if k and the maximum degree /spl Delta/ are bounded. >

  44. LA-11 直並列グラフをリスト辺彩色するアルゴリズム(A. アルゴリズム・基礎)

    藤野 友也, 周 暁, 西関 隆夫

    情報技術レターズ　1　21-22　2002年9月13日

    出版者・発行元： FIT(電子情報通信学会・情報処理学会)運営委員会

    詳細を見る 詳細を閉じる

    本文では,(単純)直並列グラフGの各辺vw∈E(G)に対して,リストLが|vw)|&ge;max{3,d(v),d(w)}を満たすならば,Gがリスト辺彩色可能であることを示す.またそのようなリストLに対してGのリスト辺彩色を求めるO(Δn)時間アルゴリズムを与える.ここで,d(v), d(w)はそれぞれGにおける点v,wの次数,ΔはGの最大次数,nはGの点数である.

  45. A-37 直並列グラフのリスト全彩色(グラフアルゴリズム(1),A.アルゴリズム・基礎)

    松尾 悠生, 周 暁, 西関 隆夫

    情報科学技術フォーラム一般講演論文集　2002　(1)　73-74　2002年9月13日

    出版者・発行元： FIT(電子情報通信学会・情報処理学会)運営委員会

  46. 木の分割問題を解くアルゴリズム

    蒲倉 正憲, 周 暁, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　101　(707)　33-40　2002年3月4日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    点集合として需要点の集合V_dと供給点の集合V_sをもち,辺集合EをもつグラフG=(V_d,V_s;E)について,各需要点には正の実数の需要量が,各供給点には正の実数の供給量が与えられたとする.グラフGのいくつかの辺を取り除くことで,各連結成分の供給点の数が高々1つであり,供給点のある連結成分について需要量の合計が,その供給量以下になるような分割を求めたい.本論文では,木において連結成分の供給点の数がちょうど1つになるような分割があるかどうかを判定するO(n)時間のアルゴリズムと,需要量と供給量を整数にしたときに,供給点のある連結成分に含まれる需要量の合計が最大となるような分割を求めるO(m^2_sn)時間のアルゴリズムを示す.ここで,m_sは供給量の最大値である.

  47. The edge-disjoint paths problem is NP-complete for series–parallel graphs

    Takao Nishizeki, Jens Vygen, Xiao Zhou

    Discrete Applied Mathematics　115　(1-3)　177-186　2001年11月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/s0166-218x(01)00223-2 　 10.1007/s10878-015-9950-2_references_DOI_EY6joiYBiV2Ed9yAUgCg92us2BZ 　 10.1587/transinf.e97.d.406_references_DOI_EY6joiYBiV2Ed9yAUgCg92us2BZ 　 10.1145/2438645.2438648_references_DOI_EY6joiYBiV2Ed9yAUgCg92us2BZ 　 10.1007/s00493-014-2828-6_references_DOI_EY6joiYBiV2Ed9yAUgCg92us2BZ 　 10.1016/j.jctb.2015.12.002_references_DOI_EY6joiYBiV2Ed9yAUgCg92us2BZ 　

    ISSN： 0166-218X

    詳細を見る 詳細を閉じる

    AbstractMany combinatorial problems are NP-complete for general graphs. However, when restricted to series–parallel graphs or partial k-trees, many of these problems can be solved in polynomial time, mostly in linear time. On the other hand, very few problems are known to be NP-complete for series–parallel graphs or partial k-trees. These include the subgraph isomorphism problem and the bandwidth problem. However, these problems are NP-complete even for trees. In this paper, we show that the edge-disjoint paths problem is NP-complete for series–parallel graphs and for partial 2-trees although the problem is trivial for trees and can be solved for outerplanar graphs in polynomial time.

  48. 直並列グラフの重み付き彩色の効率のよいアルゴリズム

    周 暁, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　101　(376)　1-8　2001年10月12日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    グラフGの各点υには正整数の重みω(υ)がついているとする.Gの重み付き彩色とは各点υへのω(υ)個の色からなる集合の割り当てであり, 隣接している2つの点に割り当てられた集合に共通な色がないようなものである.本論文では, 最少色数を用いて直並列グラフGを重み付き彩色するO(nω_max)時間の逐次アルゴリズムを与える.ここで, nはGの点数で, ω_maxはGの点に与えた正整数のうちの最大値である.

  49. 直並列グラフをリスト辺彩色するアルゴリズム

    藤野 友也, 周 暁, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　101　(376)　9-14　2001年10月12日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    グラフGの各辺eに色のリスト(集合)L(e)が与えられているとき, GのL-辺彩色とは, Gの各辺eをリストL(e)に含まれる色で塗る辺彩色である.本論文では, 各辺e=ι'u'に対して|L(e)|&gnE;max{4, d(ι'), d(u')}ならば, 任意の直並列単純グラフGはL-辺彩色を持つことを証明する.ここで, d(ι').d(u')は点ι', u'の次数である.特にGの最大次数が3以下のときには, |L(e)|&gnE;max{3.d(ι').d(u')}ならばGはL-辺彩色を持つことを証明する.この証明から, 直並列グラフのリスト辺彩色を求める効率のよいアルゴリズムが得られる.

  50. Total Colorings of Degenerated Graphs

    Takao Nishizeki, Shuji Isobe, Xiao Zhou

    Combinatorica　27　167-182　2001年1月1日

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/3-540-48224-5_42 　 10.1007/s00493-007-0050-5 　

    ISSN： 0209-9683

    eISSN： 1439-6912

    詳細を見る 詳細を閉じる

    A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.

  51. 部分k木で独立全域木を見つけるアルゴリズム

    周 暁, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　100　(402)　9-16　2000年10月20日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    2つの点を結ぶ2本の道が端点以外で点素であれば, この2本の道は内素であるという.グラフGの点rを根とする何本かの全域木が独立であるといのは, Gの各点vに対して, 航空券それらの木におけるvとrを結ぶ全ての道が互いに内素であるときである.本報告では, 部分k木, 即ち木幅が定数k以下のグラフGにおいて, 指定された点rを根とする独立全域木をできるだけたくさん求める線形時間アルゴリズムを与える.

  52. 退化的グラフの全彩色

    磯辺 秀司, 周 暁, 西関 隆夫

    電子情報通信学会技術研究報告. COMP, コンピュテーション　100　(402)　1-8　2000年10月20日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    グラフGの全彩色とは, Gの全ての点と辺を彩色して, 隣接する2点, 端点を共有する2辺, 点とそれに接続する辺が全て異なる色になるようにすることである.グラフGがs-退化的であるというのは, 次数がs以下の点を除去する操作を繰り返して, Gを自明なグラフにすることができるときである.本論文では, 最大次数Δが4s+3以上である任意のs-退化的グラフはΔ+1色を用いて全彩色できることを証明し, かつそのような全彩色を求める効率的なアルゴリズムを与える.また, 部分k-木を最小数の色を用いて全彩色する線型時間アルゴリズムも与える.

  53. Generalized Vertex-Colorings of Partial κ-Trees

    ZHOU Xiao, KANARI Yasuaki, NISHIZEKI Takao

    IEICE transactions on fundamentals of electronics, communications and computer sciences　83　(4)　671-678　2000年4月25日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0916-8508

    詳細を見る 詳細を閉じる

    Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.

  54. 部分$k$木を全彩色する線形時間アルゴリズム (新しいパラダイムとしてのアルゴリズム工学)

    磯邉 秀司, 周 暁, 西関 隆夫

    数理解析研究所講究録　1120　33-40　1999年12月

    出版者・発行元： 京都大学

    ISSN： 1880-2818

  55. A Polynomial-Time Algorithm for Finding Total Colorings of Partial $k$-Trees

    ISOBE S, ZHOU X, NISHIZEKI T

    International Journal of Foundations of Computer Science　10　(2)　171-194　1999年

    出版者・発行元： World Scientific Pub Co Pte Lt

    DOI： 10.1142/S0129054199000137 　

    ISSN： 0129-0541

    eISSN： 1793-6373

    詳細を見る 詳細を閉じる

    <jats:p> A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Many combinatorial problems can be efficiently solved for partial k-trees, that is, graphs of treewidth bounded by a constant k. However, no polynomial-time algorithm has been known for the problem of finding a total coloring of a given partial k-tree with the minimum number of colors. This paper gives such a first polynomial-time algorithm. </jats:p>

  56. Finding Edge-Disjoint Paths in Partial $k$-Trees

    ZHOU X, TAMURA S, NISHIZEKI T

    Algorithmica　26　(1)　3-30　1999年

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s004539910002 　

    ISSN： 0178-4617

    eISSN： 1432-0541

    詳細を見る 詳細を閉じる

    For a given graph G and p pairs (s i ,t i ) , $1\leq i\leq p$ , of vertices in G , the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P i , $1\leq i\leq p$ , connecting s i and t i . Many combinatorial problems can be efficiently solved for partial k -trees (graphs of treewidth bounded by a fixed integer k ), but the edge-disjoint paths problem is NP-complete even for partial 3 -trees. This paper gives two algorithms for the edge-disjoint paths problem on partial k -trees. The first one solves the problem for any partial k -tree G and runs in polynomial time if p=O( log n) and in linear time if p=O(1) , where n is the number of vertices in G . The second one solves the problem under some restriction on the location of terminal pairs even if $p\geq \log n$ .

  57. 部分k-木のl-点彩色多項式時間アルゴリズム

    金成 康彰, 周 暁, 西関 隆夫

    全国大会講演論文集　57　139-140　1998年10月5日

  58. 部分k?木の全彩色を求める多項式時間アルゴリズム

    磯辺 秀司, 周暁, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1998　(62)　33-40　1998年7月22日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    グラフGの全彩色とはGの全ての点と辺をどの隣接する2点，どの隣接する2辺，どの1点とそれに接続する辺も全て異なる色になるように彩色することである．様々な問題が部分k?木に対して効率良く解けるが，与えられた部分k?木の，最小色数を用いた全彩色を求める多項式時間アルゴリズムはまだ知られていなかった．本文ではそのような最初のアルゴリズムを与える．A total coloring of a graph G is a coloring of all elements of G, i.e. Vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a constant k). However, no polynomial-time algorithm has been known for the problem of finding a total coloring of a given partial k-tree with the minimum number of colors. This paper gives such a first polynomial-time algorithm.

  59. 部分k木に対する辺素な道問題のNP-完全性

    周暁, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1998　(41)　25-32　1998年5月20日

    出版者・発行元： 一般社団法人情報処理学会

    DOI： 10.1007/3-540-49381-6_44 　

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    数多くの組合せ問題は一般のグラフに対してNP?完全であるが，kが定数であるような部分k木に対しては多項式時間で，あるいはほとんどの場合線形時間で解ける．一方，いくつかの問題は部分k木に対してすらNP?完全である.しかしそのような問題は数少く わずかに部分グラフ同形問題と帯域幅（bandwidth）問題等が部分k木に対してNP?完全であることが知られているにすぎない．しかもこれらの問題はk＝1なる部分k木，すなわち通常の木あるいは林に対してすらNP?完全である．このようにk＝1なる部分k木に対しては多項式，時間で解け，2以上で定数の部分k木に対してはNP?完全であるような問題は知られていなかった．本論文は辺素な道問題がそのような一例であることを示す．Many combinatorial problems are NP-complete for general graphs, but are not NP-complete for partial k-trees (graphs of treewidth bounded by a constant k) and can be efficiently solved in polynomial time or mostly in linear time for partial k-trees. On the other hand, very few problems on unweighted graphs are known to be NP-complete for partial k-trees with bounded k. These include the subgraph isomorphism problem and the bandwidth problem. However, all these problems are NP-complete even for ordinary trees or forests, and there have been no known problems which are efficiently solvable for trees but NP-complete for partial k-trees. In this paper we present the first example of such problems, that is ,we show that the edge-disjoint paths problem is NP-complete for partial k-trees with some bounded k〓2 although the problem is trivially solvable for trees.

  60. Generalized Edge-Rankings of Trees

    ZHOU Xiao, KASHEM Md. Abul, NISHIZEKI Takao

    IEICE transactions on fundamentals of electronics, communications and computer sciences　81　(2)　310-320　1998年2月25日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0916-8508

    詳細を見る 詳細を閉じる

    In this paper we newly define a generalized edge-ranking of a graph G as follows:for a positive integer c, a c-edge-ranking of G is a labeling (ranking) of the edges of G with integers such that, for any label I, deletion of all edges with labels >I leaves connected components, each having at most c edges with label I. The problem of finding an optimal c-edge-ranking of G, that is, a c-edge-ranking using the minimum number of ranks, has applications in scheduling the manufacture of complex multipart products;it is equivalent to finding a c-edge-separator tree of G having the minimum height. We present an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n^2logΔ), where n is the number of vertices in T and Δ is the maximum vertex-degree of T. Our algorithm is faster than the best algorithm known for the case c=1.

  61. The edge-disjoint paths problem is NP-complete for partial k-trees

    Zhou, X, T Nishizeki

    ALGORITHMS AND COMPUTATIONS　1533　417-426　1998年

    ISSN： 0302-9743

  62. 部分k?木の一般化点ランキング

    カシェムモハメドアブル, 周暁, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1997　(26)　27-34　1997年3月14日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    グラフGの全ての点に正整数のラベルを付ける。各ラベルiについて、iより大きなラベルの点を全てGから除去したとき、各連結成分がラベルiの点を高々c個しかもたないならば、このラベル付けをc?点ランク付けという。ここでcは正整数とする。最小の個数のラベルで部分k木をc?点ランク付けする多項式時間アルゴリズムを本文は与える。ここでkは定数とする。1?点ランク付けは単に点ランク付けと呼ばれるが、本文のアルゴリズムは、1?点ランク付けを求める既知のアルゴリズムより高速である。A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with inters such that, for any label i, deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. We present a polynomial time algorithm to find a c-vertex-ranking of a partial k-tree using the minimum number of ranks for ranks for any positive integer c and any bounded integer k. Our algorithm is faster than the best algorithm known for the ordinary vertex-ranking, that is, 1-vertex-ranking.

  63. Generalized edge-rankings of trees—Extended abstract

    Takao Nishizeki, Xiao Zhou, Abul Kashem

    1197　390-404　1997年

    DOI： 10.1007/3-540-62559-3_31 　

    ISSN： 0302-9743

  64. 部分k?木を［g f］-辺彩色する多項式時間アルゴリズム

    周暁, 布施 一樹, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1996　(100)　73-80　1996年10月17日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    グラフの辺彩色とは各点に接続する辺の色が必ず異なるようにグラフの辺を彩色することである．これに対しグラフの[g，f]?辺彩色とは各点υに接続している辺のうち同じ色で彩色されるのがg（υ）本以上かつf（υ）本以下になるように辺に彩色することである．本論文は部分k木を最少色数で[g，f]?辺彩色する多項式時間アルゴリズムを与える．In an ordinary edge-coloring of a graph G = (V,E) each color appears at each vertex υ∈V at most once. A [g,f]-coloring is a generalized edge-coloring in which each color appears at each vertex υ∈V at least g(υ) and at most f(υ) times, where g(υ) and f(υ) are nonnegative and positive integers, respectively, assigned to υ. This paper gives a polynomial-time algorithm to find a [g,f]-coloring of a given partial k-tree with the minimum number of colors if such a coloring exists.

  65. 部分k-木に対する[g,f]-辺彩色アルゴリズム

    布施 一樹, 周 暁, 西関 隆夫

    全国大会講演論文集　53　359-360　1996年9月4日

    詳細を見る 詳細を閉じる

    本文では部分k-木と呼ばれるグラフのクラスを扱う.部分k-木は木の一般化であり,普通の木は部分1-木である.部分k-木に対する普通の辺彩色,及びf-辺彩色は線形時間で求めることができることが知られている.fをVから自然数への任意の関数,gをVからO以上の整数への任意の関数とする.ただし,グラフの各点vにおいてg(v)&le;f(v)で,g,fはグラフと一緒に与えちれる.グラフGの[g,f]-辺彩色とは,任意の点v∈Vに接続する同じ色の付いた辺の数がg(v)本以上f(v)本以下となるようにGのすべての辺に色を付けることである.この部分k-木に対して[g,f]-辺彩色する多項式時間アルゴリズムを与える.

  66. 部分k木で辺素な道を見つけるアルゴリズム

    周暁, 田村 朱麗, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1996　(67)　65-72　1996年7月24日

    出版者・発行元： 一般社団法人情報処理学会

    DOI： 10.1007/bfb0009496 　

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    本論文では部分k木Gの指定された端子対を結ぶ辺素な道を求める多項式時間アルゴリズムを3つ与える．Gの点数をnとして，端子対数をpとしたとき，最初のアルゴリズムでは，p=O(og )である限り，端子はGのどこにあってもよい．次のアルゴリズムでは端子対は何個あってもよいが，各端子対は分解木の同じ節点に入っていなければならない．これら2つを組み合せたのが3番目のアルゴリズムであり，ある条件を満足すれば端子対は必ずして分解木の同じ節点に入っていなくてもよいし，端子対がO(og )より多くてもよい．For a given graph G and p pairs (s_i,t_i), 1〓i〓p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P_i, 1〓i〓p, connecting s_i and t_i. Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a fixed integer k), but it has not been known whether the edge-disjoint paths problem can be solved in polynomial time for partial k-trees unless p=O(1). This paper gives three algorithms for the edge-disjoint paths problem on partial k-trees. The first one solves the problem for any partial k-tree G and runs in polynomial time if p=O(log n) and in linear time if p=O(1) where n is the number of vertices in G. The second solves the problem for any p in polynomial time if the graph G^+ obtained from G by adding p edges (s_i,t_i), 1〓i〓p, is also a partial k-tree. The third is a combination of the first and second, and solves the edge-disjoint paths problem under some restriction even if G^+ is not always a partial k-tree and p is not always O(log n).

  67. 部分k木を全彩色する多項式時間アルゴリズム

    周 暁, 西関 隆夫

    電子情報通信学会総合大会講演論文集　1996　(1)　13-13　1996年3月11日

    出版者・発行元： 一般社団法人電子情報通信学会

    詳細を見る 詳細を閉じる

    本文では部分k木と呼ばれるグラフのクラスを扱う.部分k木は木の一般化であり,普通の木は部分1木であり,外平面グラフや直並列グラフは部分2木である.部分k木は直並列グラフの一般化ともいえる.NP-完全問題に対しては効率よいアルゴリズムは一般には存在しないだろうと予想されている.しかし,部分k木に対しては点彩色問題を含む多くのNP-完全問題が線形時間または多項式時間で解けることが知られている.そのような問題の多くは "extended monadic logic of second order" で表現できる.また,辺彩色問題のようにextended monadic logic of second orderで表せないグラフ分割問題も部分k木に対しては線形時間または多項式時間で解けることがわかってきた.しかし,全彩色問題(total coloring)は部分k木に対して多項式時間で解けることが知られていなかった.グラフの全彩色問題(total coloring)とは同じ色で塗られた点と辺が隣接しないようにグラフの全ての点と辺を彩色する問題である.グラフGを全彩色するのに必要な最小の色数をGの全彩色数といい,X_t(G)と書く.本文では部分k木に対して全彩色問題を解く逐次アルゴリズムを与える.全彩色問題はグラフ理論の基本的な問題である.

  68. Generalized vertex-rankings of trees

    Takao Nishizeki, Xiao Zhou, Nobuaki Nagai

    Information Processing Letters　56　321-328　1995年12月1日

    出版者・発行元： Elsevier BV

    DOI： 10.1016/0020-0190(95)00172-7 　

    ISSN： 0020-0190

    詳細を見る 詳細を閉じる

    We newly define a generalized vertex-ranking of a graph G as follows: for a positive integer c, a c-vertex-ranking of G is a labeling (ranking) of the vertices of C with integers such that, for any label i, every connected component of the graph obtained from G by deleting the vertices with label > i has at most c vertices with label i. Clearly an ordinary vertex-ranking is a l-vertex-ranking and vice-versa. We present an algorithm to find a c-vertex-ranking of a given tree T using the minimum number of ranks in time O(cn) where n is the number of vertices in T.

  69. 木の一般化辺ランキング

    周暁, カシェムモハメドアブル, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1995　(71)　73-80　1995年7月20日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    本論文ではグラフの辺ランク付けの一般化として，新たにc?辺ランク付けを次のように定義する．グラフGのc?辺ランク付けとは，Gの辺に整数のランクを付けて，しかも任意のランクiについて，Gからランクがiより大きい辺を全て除去すると，どの連結成分にもランクiの辺が高々c本しかないようにすることである．明らかに普通の辺ランク付けは1?辺ランク付けである．本文では与えられた木を，最小のランク数でc?辺ランク付けするO(^2logΔ）時間のアルゴリズムを与える．ここで，nはグラフGの点数で，Δは最大次数である．We newly define a generalized edge-ranking of a graph G as follows: for a positive integer c, a c-edge-ranking of G is a labeling (ranking) of the edges of G with integers such that, for any label i, deletion of all edges with labels < i leaves connected components, each having at most c edges with label i. The problem of finding an optimal c-edge-ranking of G, that is, a c-edge-ranking using the minimum number of ranks, has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding a c-edge-separator tree of G having the minimum height. We present an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n^2logΔ), where n is the number of vertices in T and Δ is the maximum vertex-degree of T.

  70. 部分k-木をf-辺彩色するアルゴリズム

    周暁, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1995　(71)　97-104　1995年7月20日

    出版者・発行元： 一般社団法人情報処理学会

    DOI： 10.1007/bfb0015439 　

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    グラフの辺彩色は各点に接続する辺の色が必ず異なるように辺に彩色することである．グラフのf?辺彩色は各点νに接続している辺の高々f（ν）本しか同じ色で塗られないように辺に彩色することである．本論文は部分k木について最少色数でf?辺彩色する線形時間の逐次アルゴリズム及び最適な並列アルゴリズムを与える．In an ordinary edge-coloring of a graph G = (V,E) each color appears at each vertex ν ∈ V at most once. An f-coloring is a generalized edge-coloring in which each color appears at each vertex ν ∈ V at most f(ν) times, where f(ν) is a positive integer assigned to ν. This paper gives a linear-time sequential algorithm and an optimal parallel algorithm which find an f-coloring of a given partial k-tree using the minimum number of colors if all f(ν)'s are bounded.

  71. 木の一般化ランク付け

    周暁, 永井 伸明, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1994　(100)　87-94　1994年11月18日

    詳細を見る 詳細を閉じる

    本論文ではグラフの点ランク付けの一般化として，新たにc?ランク付けを定義する．即ち，グラフGのc?ランク付けとは，Gの点に整数のランクを付けて，しかも任意のランクiについて，Gからランクがiより大きい点を全て除去すると，どの連結成分にもランクiの点が高々c個しかないようにすることである．明らかに普通の点ランク付けは1?ランク付けである．本文では与えられた木を，最小のランク数でc?ランク付けする線形時間のアルゴリズムを与える．In this paper we newly define a generalized vertex-ranking of a graph G as follows: for a positive integer c, a c-vertex-ranking of G is a labeling (ranking) of the vertices of G with integers such that, for any label i, every connected component of the graph obtained from G by deleting the vertices with label > i has at most c vertices with label i. Clearly an ordinary vertex-ranking is a l-vertex-ranking. We present a linear algorithm to find a c-vertex-ranking of a given tree using a minimum number of ranks for any bounded integer c.

  72. 木を辺ランク付けする効率のよいアルゴリズム

    周暁, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1994　(69)　9-16　1994年7月22日

    出版者・発行元： 一般社団法人情報処理学会

    DOI： 10.1007/bfb0049402 　

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    グラフの辺ランク付けとは各辺にラベルを付け、同じラベルの辺を結ぶどの道にもそれより大きいラベルの辺があるようにすることである．辺ランク付け問題とは与えられたグラフをできるだけ少ないラベルを用いて辺ランク付けする問題である．この問題は組み立て作業のスケジューリング問題などに応用される．本論文は与えられた木を最小個数のランクを用いて辺ランク付けするO（^）時間のアルゴリズムを与える．An edge-ranking of an undirected graph G is a labeling of the edges of G with integers such that all paths between two edges with the same label i contain an edge with label j > i. The problem of finding an edge-ranking of G using a minimum number of ranks has applications in scheduling the manufacture of complex multi-part products; it is equivalent to finding the minimum height edge separator tree. Deogun and Peng and independently de la Torre et al. have given polynomial-time algorithms which find an edge-ranking of trees T using a minimum number of ranks in time O(n^3) and O(n^3logn) respectively, where n is the number of nodes in T. This paper presents a more efficient and simple algorithm, which finds an edge-ranking of trees using a minimum number of ranks in O(n^2) time.

  73. グラフの辺彩色及びf－辺彩色アルゴリズム

    周暁, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1994　(26)　9-16　1994年3月17日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    グラフの辺彩色は各点に接続する辺の色が必ず異なるように辺に彩色することである．グラフのf?辺彩色は各点υに接続している辺の高々f（υ）本しか同じ色で塗られないように辺に彩色することである．本論文は二部グラフ、平面グラフ、種数gのグラフ、部分k木、s?縮退グラフ、樹化数aのグラフ等、種々のクラスのグラフについて最少色数で辺彩色する効率の良い逐次アルゴリズム及び並列アルゴリズムを与える．In an ordinary edge-coloring of a graph G = (V,E) each color appears at each vertex υ ∈ V at most once. An f-coloring is a generalized coloring in which each color appears at each vertex υ ∈ V at most f(υ) times. This paper gives efficient sequential and parallel algorithms which find ordinary edge-colorings and f-colorings for various classes of graphs such as bipartite graphs, planar graphs, graphs of fixed genus, partial k-trees, s-degenerate graphs, graphs of fixed arboricity etc.

  74. Edge-coloring and f-coloring for various classes of graphs

    Takao Nishizeki, Xiao Zhou

    Journal of Graph Algorithms and Applications　3　1-18　1994年1月1日

    出版者・発行元： Springer Berlin Heidelberg

    DOI： 10.1007/3-540-58325-4_182 　 10.1142/9789812777638_0012 　 10.7155/jgaa.00012 　

    eISSN： 1526-1719

    詳細を見る 詳細を閉じる

    In an ordinary edge-coloring of a graph G=(V, E) each color appears at each vertex v e V at most once. An f-coloring is a generalized coloring in which each color appears at each vertex v e V at most f(v) times. This paper gives efficient sequential and parallel algorithms which find ordinary edge-colorings and f-colorings for various classes of graphs such as bipartite graphs, planar graphs, graphs of fixed genus, partial k-trees, s-degenerate graphs, graphs of fixed arboricity etc.

  75. 部分k木を辺彩色する並列アルゴリズム

    周暁, 中野 眞一, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1993　(48)　25-32　1993年5月28日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    部分k木に対しては数多くの組合せ問題を解く並列アルゴリズムが知られている．しかし，辺彩色問題に対しては効率のよい並列アルゴリズムが得られていなかった．本論文は与えられた部分k木を最小色数で辺彩色する効率のよい並列アルゴリズムを与える．A parallel algorithm is considered efficient if its time complexity is polylogarithmic with polynomially many processors on the PRAM. NC is the class of problems that have such algorithms. Many combinatorial problems can be efficiently solved in parallel for partial k-trees. The edge-coloring problem is one of a few combinatorial problems for which no NC algorithms have been obtained for partial k-trees. This paper gives a first NC parallel algorithm which finds and optimal edge-coloring of a given partial k-tree.

  76. 部分 k 木を辺彩色する線形時間アルゴリズム

    周暁, 中野 眞一, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1993　(24)　89-96　1993年3月18日

    詳細を見る 詳細を閉じる

    部分k木に対しては数多くの組合せ問題が線形時間で解けることが知られている．しかし辺彩色問題に対しては効率よいアルゴリズムが得られていなかった．本論文は与えられた部分k木の辺彩色指数を求め，その指数に等しい色数で辺彩色する線形時間アルゴリズムを与える．Many combinatorial problems can be efficiently solved for partial k-trees. The edge-coloring problem is one of a few combinatorial problems for which no linear time algorithm has been obtained for partial k-trees. This paper gives an algorithm which optimally edge-colors a given partial k-tree in linear time.

  77. Efficient Algorithms for Edge-Coloring Partial k-Trees

    周 暁, 中野 眞一, 鈴木 均, 西関 隆夫

    全国大会講演論文集　45　57-58　1992年9月28日

    詳細を見る 詳細を閉じる

    Many combinatonal problems can be efficiently solved for partiai k-trees.The edge-coloring problem is one of a few combinatorial problems for which no efficient algorithms have been obtained for partial k-trees.This report presents two algoritms.One decides the chromatic index of a given partial k-tree in linear time.The other optimally edge-colors a given partial k-tree G in O(|V|^2)time,where V is the set of vertices of G.In the report k is assumed to be a constant.

  78. 直並列グラフを辺彩色する線形時間アルゴリズム

    周暁, 鈴木 均, 西関 隆夫

    情報処理学会研究報告アルゴリズム（AL）　1992　(78)　49-56　1992年9月25日

    詳細を見る 詳細を閉じる

    直並列グラフに対しては数多くの組合せ問題が線形時間で解けることが知られている．しかし，辺彩色問題に対しては効率のよいアルゴリズムが得られていなかった．本論文は直並列多重グラフの辺彩色問題を解く線形時間のアルゴリズムを与える．Many combinatorial problems can be solved in linear time for series-parallel graphs or partial k-trees. The edge-coloring problem is one of a few combinatorial problems for which no linear algorithm has been obtained for series-parallel multigraphs. This paper gives a linear algorithm for the problem.

︎全件表示 ︎最初の5件までを表示

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

  1. グラフのライドシェアリング問題とその応用に関する研究

    周 暁

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2019年4月1日 ～ 2022年3月31日

    詳細を見る 詳細を閉じる

    本研究ではグラフのライドシェアリング問題を解く効率のよいアルゴリズムの設計論を構築するとともに、大規模災害発生時の緊急支援物資輸送などへの応用可能な経路策定方法論を研究する目的であり、本研究で得られた成果として，グラフ特に木や木幅が小さいグラフに関する理論的な展開とアルゴリズムの効率化があげられる。 本研究で開発したアルゴリズムは、木やコグラフなどにおける数多くの組合せ問題に適用可能と思い、効率よいアルゴリズム、多項式時間アルゴリズム、FPTアルゴリズムの開発に貢献でき、しかも得られた成果をまとめた5編の学術論文を発表しており、高く評価できる。

  2. 木構造に基づくグラフアルゴリズムの設計法に関する研究

    周 暁

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2016年4月1日 ～ 2019年3月31日

    詳細を見る 詳細を閉じる

    本研究で得られた成果として，グラフ特に木や木幅が小さいグラフに関する理論的な展開とアルゴリズムの効率化があげられる．木幅というのはグラフを木分解する際，分解木の節点に含まれるグラフの頂点数から１を引いた最大値である．木幅１のグラフは林であり，木幅２のグラフは直並列グラフである．本研究では，特に木構造をもつグラフに対してグラフの分割と巧みな動的計画法を導入して，数多くの組合せ問題を効率よく解くアルゴリズムを研究開発することに成功した．特に本研究で開発したアルゴリズムは，数多くの組合せ問題に適用可能であり，しかも得られた成果をまとめた12編の学術論文を発表しており，高く評価できる．

  3. グラフを分割，彩色，描画するアルゴリズムの効率化とそれらの応用

    西関 隆夫, 周 暁, 伊藤 健洋, 内沢 啓

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    2009年4月1日 ～ 2014年3月31日

    詳細を見る 詳細を閉じる

    グラフの分割，彩色あるいは描画する問題の最適解や近似解を求める効率のよいアルゴリズムを開発するとともに，それらを実用的な問題に応用した．代表的な成果の一例を挙げる．点重み付きグラフGと正整数pが与えられたときに，何本かの辺を除去してGをp個の連結成分に分割し，各成分の点重みの合計をできるだけ公平にするアルゴリズムを木幅限定グラフに対し開発した．

  4. グラフ分割アルゴリズムの設計法とその応用に関する研究

    周 暁

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2011年 ～ 2013年

    詳細を見る 詳細を閉じる

    本研究の成果として，グラフ特に木や直並列グラフや木幅が小さいグラフに関する理論的な展開とアルゴリズムの効率化があげられる．電力網などを需要点と供給点のあるグラフでモデル化し，供給されている需要点の需要量の合計が最大になるような電力の流し方を求める最大化問題を扱っていた．本研究では，この最大化問題は木に対してすらNP困難であることを示した．さらに，部分ｋ木に対し，グラフの分割と巧みな動的計画法を導入して，この問題を擬多項式時間で解くアルゴリズムを与えた．この成果が高く評価され，FAW-AAIM 2012の最優秀論文賞が受賞されていた．

  5. 部分k木に対するアルゴリズムの設計論に関する研究

    周 暁, 西関 隆夫

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2007年 ～ 2009年

    詳細を見る 詳細を閉じる

    本研究では,幾つかの組み合せ問題を解くアルゴリズムの設計論を構築することと共に幾つかの組み合せ最適化問題を論理式で定式化することが成功した.更に,kを限定し,部分k木より小さいグラフのクラス,即ち木(部分1木)や直並列グラフ(部分2木)のクラスにおいて,数多くの組み合せ問題をを効率でよく解く多項式時間アルゴリズムの開発を成功した.これらの成果をまとめたのが8編の学術誌論文と3編の国際会議論文である.得られた多くの結果は線形時間アルゴリズムの統一的設計理論を与えるものであり,線形時間アルゴリズム理論の分野に与えたインパクトは極めて大きい.

  6. VLSI設計へのグラフ描画アルゴリズムの応用

    西関 隆夫, 周 暁, 伊藤 健洋, 内沢 啓, 周 暁, 伊藤 健洋

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2007年 ～ 2008年

    詳細を見る 詳細を閉じる

    これまでに平面グラフの埋め込みアルゴリズム, 矩形描画アルゴリズム, 凸描画アルゴリズム, 4連結平面グラフの直線描画アルゴリズム, 直交描画アルゴリズムなど数多くの効率のよいアルゴリズムを開発してきた。これらのもとに, 新しい描画形式である内部矩形描画, 面積指定8角形描画, 折れ曲り数最小な直交描画等に関する理論を確立し, 効率のよいアルゴリズムを開発し, VLSI配置・配線問題への応用を図った.

  7. グラフ描画アルゴリズムとそのWeb情報検索への応用

    西関 隆夫, 周 暁, 伊藤 健洋, 三浦 一之, 浅野 泰仁

    2004年 ～ 2007年

    詳細を見る 詳細を閉じる

    (1)平面的グラフの折れ曲がりなし直交描画問題について,グラフが3連結立方グラフの細分であれば,折れ曲がりなし直交描画を線形時間で求めることのできるアルゴリズムを与えた. (2)直並列グラフの直交描画で折れ曲り数最少のものを求める線形アルゴリズムを開発した. (3)平面グラフの格子凸描画において,別個に研究されてきた標準分解,リアライザ,シュナイダーラベリング,順序つき全域木がすべて同等であることを証明した. (4)VLSIレイアウトに平面グラフの内部矩形描画が応用できる.与えられた平面グラフが内部矩形描画できるかどうか判定し,できるならば内部矩形描画を高速に求めるアルゴリズムを与えた. (5)電力供給問題のモデル化であり,一般には強NP困難問題として知られる,需要・供給付きグラフの分割問題について研究し,分割数を最少・最多にする問題,および指定された個数の連結成分への分割を求める問題に対して,グラフが木(または部分k-木)であるときに厳密解を求める多項式時間(または擬似多項式時間)アルゴリズムを与えた. (6)購入した計算機を用いてウェブ文書データを解析し,サイトのデータを抽出し,このデータからサイトを点とするサイト間グラフを構築した.さらに,サイト間グラフの特徴を利用して,著名な情報検索手法であるmax-flow based methodの品質を大幅に改善する手法を確立し,実験によってその性能を検証した.

  8. 効率的グラフアルゴリズムの統一的設計理論に関する研究

    西関 隆夫, 周 暁, 伊藤 健洋, 浅野 泰仁

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2005年 ～ 2006年

    詳細を見る 詳細を閉じる

    本研究では,木,直並列グラフ,部分k-木等の構造的グラフに対し,彩色問題,素な道問題,グラフ描画問題を取り上げ,個々の問題に対して効率のよいアルゴリズムを設計するばかりでなく,構造的グラフに対する効率的アルゴリズムの統一的設計法の研究開発を行った. まず,木に対しては,需要点と供給点があるときの分割問題を解く完全近似スキームを与えることができた. 直並列グラフに対しては,リスト全彩色が存在するための十分条件を与えるとともに,その条件を満足する場合にリスト全彩色を線形時間で求めるアルゴリズムを開発した. 次に,部分k-木に対しては,全彩色問題を解く線形時間アルゴリズム,均一分割問題を解く擬多項式時間アルゴリズム,需要点と供給点のあるグラフの分割問題を解く擬多項式時間アルゴリズムの開発に成功した. また,グラフ描画アルゴリズムでは,直並列グラフの折れ曲り数最少の直交描画を求める線形アルゴリズムを設計するとともに,グラフの凸描画問題に応用することができるグラフの分解法も与えた. 本年度は,構造的グラフに対する効率的アルゴリズムの統一的設計法の開発を目指した研究を行い,これまでさまざまな問題に対するより高速なアルゴリズムの開発に成功しており,一般の辺素部分グラフ分解問題に対する効率のよいアルゴリズムの統一的理論構築のために基盤作りに十分な成果をあげることができ,得られた成果を論文としてまとめ,論文誌では7編,国際会議では5編発表した.

  9. 部分k木の組み合せ問題の解法に関する研究

    周 暁, 西関 隆夫, 浅野 泰仁, RHAMAN Md.s., 三浦 一之

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2004年 ～ 2006年

    詳細を見る 詳細を閉じる

    計算量理論やアルゴリズム論の分野において,グラフに関する様々な組み合せ問題の解法が活発に研究されてきている.これらの組み合せ問題のなかには,実用的な問題が多く含まれているが,そのほとんどはNP-困難であることが示されている.その一方で,部分k木と呼ばれるグラフのクラスに制限した場合には,多くのNP-困難な計算問題が多項式時間計算可能であることが明らかになってきている.しかしながら,これまでの研究は個々の問題の解法を個別に与えたものであり,これらの問題を解く一般的な方法についての研究はほとんど行われていなかった.本研究では,部分k木の組み合せ問題をモデル化し,そのモデルに現実の組み合せ問題の特色を反映させるために,現技術の調査を行った.今までに知られていた辺彩色アルゴリズム,[g, f]彩色アルゴリズム,多重彩色アルゴリズム,重み付き彩色アルゴリズム,辺素な道アルゴリズム,独立全域木アルゴリズムなどを含む一般的な組み合せ問題を定式化するための幾つかの条件を見つけた.それらの問題を解く効率の良いアルゴリズムを自動的に生成することができる方法論を構築するために,幾つかの組み合せ最適化問題を論理式で定式化することが成功した.更に,kを限定し,部分k木より小さいグラフのクラス,即ち木(部分1木)や直並列グラフ(部分2木)のクラスに置いて,コスト辺彩色や多重点彩色問題を効率でよく解く多項式時間アルゴリズムの開発を成功した.理論的にもその手法の効率性の検証ができた.この成果より,開発されたアルゴリズムは幾つかの条件を満たす一般的な組合せ問題を効率良く解くことが分かった.これらの成果をまとめたのが17編の学術誌論文と20編の国際会議論文である.得られた結果は線形時間アルゴリズムの統一的設計理論を与えるものであり,線形時間アルゴリズム理論の分野に与えたインパクトはい極めて大きい.

  10. グラフ描画の理論とアルゴリズムに関する研究

    西関 隆夫, 周 暁, RHAMAN Md. S., 三浦 一之, 浅野 泰仁

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2003年 ～ 2004年

    詳細を見る 詳細を閉じる

    平面グラフの外面も含めて全ての面を矩形(長方形)で描画することを矩形描画という. Thomassenは平面グラフの矩形描画が存在するための必要十分条件を与えているが,それは点に接続している辺の最大本数,即ち最大次数Δが3以下の平面グラフに限定されていた.本研究では,矩形描画を一般化して,内面は全て矩形であるが,外面は矩形であるとは限らず,L字形やT字形のような軸平行多角形であればよい"内部矩形描画"という新しい描画形式を提案した.更に,Δ≦3とは限らない,一般の場合に内部矩形描画が存在するための必要十分条件を与えた.この結果はVLSIレイアウトへの実用的応用があるばかりでなく,30年来の未解決問題を解決したことになる.また内部矩形描画を効率よく求めるアルゴリズムも開発した. 矩形描画と箱直交描画を一般化した箱矩形描画という新しい描画形式を提案し,箱矩形描画が存在するための必要十分条件を与えるとともに,効率のよいアルゴリズムを開発した.その計算時間はグラフの点数に比例する程度であるので,最適であり,これ以上改善の余地はない. 従来のVLSIレイアウト設計では矩形描画を用いていたため,隣接させたくないモジュールまでもが隣接してしまうレイアウトが求まることがあった.本研究の箱矩形描画を用いたVLSIレイアウトではそのようなことが起きない. 他の描画形式である,直線描画,凸描画,矩形勢力描画等に関しても,できるだけ小さく描画する効率のよいアルゴリズムを設計した.特に4連結平面グラフは一般の平面グラフより1/4の面積で描画できるという画期的な結果を与えた.

  11. 通信スケジューリングのグラフアルゴリズムによる解法

    周 暁

    2001年 ～ 2002年

    詳細を見る 詳細を閉じる

    今年度は効率のよい通信スケジューリングのアルゴリズムをグラフアルゴリズム、特にリスト辺彩色や多重彩色アルゴリズムを応用して研究開発を行なった。リスト辺彩色や多重彩色問題は辺彩色や点彩色問題の一般化であり、NP-困難である。一般のグラフに対してはこの問題を解く効率の良いアルゴリズムが存在しないと予想されている。我々はグラフのクラスを限定したとき、即ち直並列グラフや部分k木に対して効率よいアルゴリズムを開発成功した。それらの成果を以下の論文でまとめた。 1.Tomoya Fujino, Shuji Isobe, Xiao Zhou, and Takao Nishizaki Linear algorithm for finding list edge-colorings of series-parallel graphs IEICE Trans. on Information and Systems, E86-D(2003), pp.186-190 2.Takehiro Ito, Takao Nishizaki, Xiao Zhou Algorithms for multicolorings of partial K-trees IEICE Trans. on Information and Systems, E86-D(2003), pp.191-200 また、限定されたグラフに対して効率よいアルゴリズムや一般グラフに対して近似アルゴリズムや確率的アルゴリズム等の調査も行った。現在知られているアルゴリズムの理論的評価および計算機による実験的シミュレーションを行い、各手法によって得られるデータを分析した。また各手法の効率を理論と実験両方で検証した。

  12. グラフアルゴリズムの効率化と評価に関する研究

    西関 隆夫, 三浦 一之, 周 暁

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2001年 ～ 2002年

    詳細を見る 詳細を閉じる

    本研究では,木,直並列グラフ,部分κ-木等の構造的グラフに対し,彩色問題,素な道問題,グラフ描画問題を取り上げ,個々の問題に対して効率のよいアルゴリズムを設計するばかりでなく,構造的グラフに対する効率的アルゴリズムの統一的設計法の研究開発を行った。 まず,部分k-木に対しては,辺色彩問題を一般化した[g, f]辺彩色問題を解く多項式時間アルゴリズム,全彩色問題を解く線形時間アルゴリズム,辺素な道問題をある特定の条件下で多項式時間で解くアルゴリズム,点ランク付け問題を多項式時間で解く逐次アルゴリズム,O(logn)時間で解く並列アルゴリズムの開発に成功した。また,直並列グラフの辺素な道問題を見つけそのNP-完全性の証明にも成功した。 木に対しては,一般化ランク付け問題をO(n^2logΔ)時間で解くアルゴリズムを与え,また平面グラフ上で"非交差"なスタイナ林を求める問題を,すべてのスタイナ木の端子が2つの面にしかないとき,O(nlogn)時間で解くアルゴリズムも与えた。 直並列グラフに対しては,辺彩色問題を線形時間で解く逐次アルゴリズムを与えるとともに,O(Δn/logn)台のプロセッサーを用いてO(logn)時間で解く並列アルゴリズムを与えた。どちらのアルゴリズムも計算時間は比例定数の範囲内で最適である。 また,グラフ描画アルゴリズムでは,平面グラフの3種類の描画を求める線形アルゴリズムを設計するとともに,グラフの凸描画問題に応用することができるグラフの分解法も与えた。

  13. 通信スケジューリングのグラフアルゴリズムによる解法

    周 暁

    1999年 ～ 2000年

    詳細を見る 詳細を閉じる

    本研究はネットワーク上の通信スケジューリングのアルゴリズムをグラフ理論,特に重み付け辺彩色アルゴリズムの応用により研究開発するものである.ネットワーク上の通信をモデル化する.グラフ上の各点はコンピュータに,辺はコンピュータ間の通信要求に対応する.各コンピュータυは同時に通信できる最大数f(υ)も決められ,各コンピュータ間(υ,w)には同時使用できる回線の最大数g(υ,w)も決められているとする.各通信要求(辺e)に通信時間(重みw(e))を付ける.この時f(υ)とg(υ,w)の条件を満足し,同時に通信可能な辺を同一色で塗る.各色について、かかる通信時間は同じ色で塗られた辺の最大重みに対応している.また,通信が始まる前に必ず前回の通信が全部終了したとする。このように各色で塗られたグラフの辺の最大重みの総和を最小にするグラフ辺彩色は,最短時間での通信スケジューリングに対応している.このようなグラフ辺彩色問題を重み付け辺彩色問題という.本研究は上記のモデルを更に検討強化し,効率よく実行する通信スケジューリングを求める高速で実用的なアルゴリズムの研究開発,特に木の重み付け辺彩色問題を解く多項式時間のアルゴリズムの研究開発を行なった.また,コスト辺彩色問題もネットワーク上の通信スケジューリング問題によく応用されることが知られている.我々は与えられた木をコスト辺彩色問題をO(nΔ^2)時間で解くアルゴリズムを与えた.ここで,nは与えられた木の点数で,Δは最大次数である.

  14. 構造的グラフに対するアルゴリズムの工学的研究

    西関 隆夫, 周 暁, 草苅 良至

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    1999年 ～ 2000年

    詳細を見る 詳細を閉じる

    本研究では,木,直並列グラフ,部分k-木等の構造的グラフに対し,彩色問題,素な道問題,グラフ描画問題を取り上げ,個々の問題に対して効率のよいアルゴリズムを設計するばかりでなく,構造的グラフに対する効率的アルゴリズムの統一的設計法の研究開発を行った。 まず,部分k-木に対しては,辺色彩問題を一般化した[g,f]辺彩色問題を解く多項式時間アルゴリズム,全彩色問題を解く線形時間アルゴリズム,辺素な道問題をある特定の条件下で多項式時間で解くアルゴリズム,点ランク付け問題を多項式時間で解く逐次アルゴリズム,O(logn)時間で解く並列アルゴリズムの開発に成功した。また,直並列グラフの辺素な道を見つけ問題はNP-完全であることの証明にも成功した。 木に対しては、一般化ランク付け問題をO(n^2logΔ)時間で説くアルゴリズムを与え,また平面グラフ上で"非交差"なスタイナ林を求める問題を,すべてのスタイナ木の端子が2つの面にしかないとき,O(nlogn)時間で解くアルゴリズムも与えた。 直並列グラフに対しては,辺彩色問題を線形時間で解く逐次アルゴリズムを与えるとともに,O(Δn/logn)台のプロセッサーを用いてO(logn)時間で解く並列アルゴリズムを与えた。どちらのアルゴリズムも計算時間は比例定数の範囲内で最適である。 また,グラフ描画アルゴリズムでは,平面グラフの3種類の描画を求める線形アルゴリズムを設計するとともに,グラフの凸描画問題に応用することができるグラフの分解法も与えた。 本年度は,構造的グラフに対する効率的アルゴリズムの統一的設計法の開発を目指した研究を行い,これまでさまざまな問題に対するより高速なアルゴリズムの開発に成功しており,一般の辺素部分グラフ分解問題に対する効率のよいアルゴリズムの統一的理論構築のために基盤作りに十分な成果をあげることができた。

  15. スケジューリングのグラフアルゴリズムによる解法

    周 暁, 水木 敬明, 草苅 良至

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research on Priority Areas (B)

    研究機関：Tohoku University

    1998年 ～ 2000年

    詳細を見る 詳細を閉じる

    本研究ではグラフを用いてスケジューリング問題のモデル化を行った.この問題への応用が強く期待される彩色問題を一般グラフに対して効率よく解くアルゴリズムは存在しないと予想されるので、現実でよく使うグラフのクラスに少し制限することにより,今まで解けなかった様々なNP-因難の問題を実用的に解き得ることができた.本研究で得られた成果は主に以下の4つである. 1.動的計画法を用いて部分k木に対して[g,f]辺彩色問題を解く線形時間アルゴリズムを開発した。この成果は雑誌Algorithmica(1999)に掲載された. 2.動的計画法を用いて部分k木に対して全彩色問題を解く線形時間アルゴリズムを開発した,この成果を国際会議ISAAC'99(The 10^<th> International Symposium on Algorithms and Computation)で発表した.その後,部分k木よりもっと広いグラフのクラス,縮退グラフに対してもこの問題を解く効率のよいアルゴリズムを開発した.この成果が国際会議ICALP'01(The 28^<th> International Colloquium on Automata,Languages and Programming)で発表した. 3.部分k木に対して1-点彩色問題を解く多項式時間アルゴリズムを開発した.この成果が雑誌IEICE Trans.On Fundamentals of Electronics,Communication and Computer Sciences(2000)に掲載された. 4.木に対してコスト辺彩色問題を解く多項式時間アルゴリズムを開発した.この成果を国際会議COCOON'01(The 7^<th> Annual International Computing and Combinatorics Conference)で発表した.

  16. ネットワーク上の通信スケジューリングの分散アルゴリズム

    周 暁

    1997年 ～ 1998年

    詳細を見る 詳細を閉じる

    平成10年で度は通信スケジューリングをグラフを利用してモデル化し,通信を効率よく実行するスケジューリングを与えるアルゴリズムの研究開発を行なった.グラフの彩色問題とスケジュール問題には密接な関連がある.いくつかの彩色アルゴリズムはスケジューリングアルゴリズムに応用されている.最近では高級言語のコンパイルのレジスタ変数の自動スケジュールなどに応用された.辺彩色問題はNP-完全であり,一般のグラフに対してこの問題を解く効率のよいアルゴリズムは存在しないと予想されている.我々はグラフのクラスを限定したとき,効率の良いアルゴリズムを考えた.即ち,部分κ-木に対して全彩色問題を解く多項式時間アルゴリズムを開発した.グラフGの全彩色とはGの全ての点と辺をどの隣接する2点,どの隣接する2辺,どの1点とそれに接続する辺も全て異なる色になるように最小色数で彩色することである.与えられた部分κ-木の,最小色数を用いた全彩色を求める多項式時間アルゴリズムは今まで知られていなかった.私たちはそのような最初のアルゴリズムを与えた.この成果を国際会議WG'98(Proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science)で発表した. 辺ランク付け問題もスケジューリング問題によく応用されることが知られている.私たちは与えられた木を,最小のランク数でc-辺ランク付けする多項式時間のアルゴリズムを与える.この結果がIEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciencesに掲載された.また,もっと広いグラフのクラス,部分κ木に対しても我々は最小のランク数でc-辺ランク付けする多項式時間のアルゴリズムを与えた.この成果を国際会議ICCIT'98(Procedings of International Conference on Computer and Information Technology)で発表した.

  17. 構造的グラフに対する効率的アルゴリズムの統一的設計法

    西関 隆夫, 周 暁, 中野 眞一

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    1997年 ～ 1998年

    詳細を見る 詳細を閉じる

    本研究では,木,直並列グラフ,部分k-木等の構造的グラフに対し,彩色問題,素な道問題,グラフ描画問題を取り上げ,個々の問題に対して効率のよいアルゴリズムを設計するばかりでなく,構造的グラフに対する効率的アルゴリズムの統一的設計法の研究開発を行った. まず,部分k-木に対しては,辺彩色問題を一般化した[g,f]全彩色問題を解く多項式時間アルゴリズム,辺素な道問題をある特定の条件下で多項式時間で解くアルゴリズム,点ランク付け問題を多項式時間で解く逐次アルゴリズム,O(log n)時間で解く並列アルゴリズムの開発に成功した.また,部分k-木の辺素な道問題を見つけそのNP-完全性の証明にも成功した. 木に対しては,一般化ランク付け問題をO(n^2logΔ)時間で解くアルゴリズムを与え,また平面グラフ上で“非交差"なスタイナ林を求める問題を,すべてのスタイナ木の端子が2つの面にしかないとき,O(n log n)時間で解くアルゴリズムも与えた. 直並列に対しては,辺彩色問題を線形時間で解く逐次アルゴリズムを与えるとともに,O(Δn/log n)台のプロセッサーを用いてO(log n)時間で解く並列アルゴリズムを与えた.どちらのアルゴリズムも計算時間は比例定数の範囲内で最適である. また,グラフ描画アルゴリズムでは,平面グラフの3種類の描画を求める線形時間アルゴリズムを設計するとともに,グラフの凸描画問題に応用することができるグラフの分解法も与えた. 本研究では,2年にわたり構造的グラフに対する効率的アルゴリズムの統一的設計法の開発を目指し研究を行ってきたが,これまで様々な問題に対するより高速なアルゴリズムの開発に成功しており,一般の辺素部分グラフ分解問題に対する効率のよいアルゴリズムの統一的理論構築のための基盤作りに十分な成果をあげることができた.

︎全件表示 ︎最初の5件までを表示