Details of the Researcher

PHOTO

Gyo Shu
Section
Graduate School of Information Sciences
Job title
Professor
Degree

  • Doctor of Philosophy (Information Sciences) (Tohoku University)

e-Rad No.
10272022
Profile
Graph Theory, Graph Algorithm

Education 1

  • Tohoku University　Graduate School of Information Sciences　Department of System Information Sciences

    1992/04 - 1995/03

Research Areas 1

  • Informatics / Information theory /

Papers 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/02/29

    Publisher: 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. Parameterized Complexity of Weighted Target Set Selection.

    Takahiro Suzuki, Kei Kimura, Akira Suzuki, Yuma Tamura, Xiao Zhou 0001

    TAMC　2024　(AL-196)　320-331　2024

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

    ISSN： 0304-3975

    eISSN： 1879-2294

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

    WALCOM　2024　(AL-196)　421-435　2024

    Publisher:

    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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　14422 LNCS　359-370　2024

    Publisher:

    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 Peer-reviewed

    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/03

    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. The Hamiltonian Cycle Reconfiguration Problem for Interval Graphs

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

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

    ISSN： 1349-144X

  16. Optimization Variant of Vertex-Coloring Reconfiguration Problem

    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 0001

    Computing and Combinatorics - 27th International Conference(COCOON)　13025 LNCS　(1)　355-366　2021

    Publisher: Springer

    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 0001

    Theor. Comput. Sci.　849　227-236　2021

    Publisher:

    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

    Publisher: 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 Peer-reviewed

    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

    Publisher: 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 Peer-reviewed

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

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

    Publisher: 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. Method for Distribution Loss Minimization and Switching Operation Procedures with Radial Network Reconfiguration

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

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

  25. Reconfiguration of minimum Steiner trees via vertex exchanges Peer-reviewed

    Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)　138　79:1-79:11　2019

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.MFCS.2019.79 　

    ISSN： 1868-8969

  26. Parameterized complexity of the list coloring reconfiguration problem with graph parameters Peer-reviewed

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　739　65-79　2018/08/29

    Publisher: Elsevier B.V.

    DOI： 10.1016/j.tcs.2018.05.005 　

    ISSN： 0304-3975

  27. グラフの色付きトークン整列問題について

    Konno, Hayato, Suzuki, Akira, Yamanaka, Katsuhisa, Ito, Takehiro, Zhou, Xiao

    RIMS Kokyuroku　2088　53-62　2018/08

    Publisher:

    ISSN： 1880-2818

  28. Computational Power of Threshold Circuits of Energy at most Two

    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. Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem

    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. Peer-reviewed

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

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

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.ISAAC.2018.37 　

    ISSN： 1868-8969

  31. Computational Power of Threshold Circuits of Energy at most Two. Peer-reviewed

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

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

    Publisher: Institute of Electronics, Information and Communications Engineers (IEICE)

    DOI： 10.1587/transfun.E101.A.1431 　

    ISSN： 0916-8508

    eISSN： 1745-1337

  32. The complexity of (List) edge-coloring reconfiguration problem Peer-reviewed

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　E101A　(1)　232-238　2018/01/01

    Publisher: Institute of Electronics, Information and Communication, Engineers, IEICE

    DOI： 10.1587/transfun.E101.A.232 　

    ISSN： 1745-1337 0916-8508

    eISSN： 1745-1337

  33. Reconfiguration of Steiner Trees in an Unweighted Graph Peer-reviewed

    Haruka Mizuta, Takehiro Ito, Xiao Zhou

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

    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 Peer-reviewed

    Wang Xiaoyan, Wang Chengyou, Zhou Xiao, Yang Zhiqiang

    JOURNAL OF INFORMATION PROCESSING SYSTEMS　13　(1)　114-127　2017/02

    DOI： 10.3745/JIPS.02.0053 　

    ISSN： 1976-913X

  35. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters. Peer-reviewed

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    CoRR　abs/1705.07551　2017

  36. The Complexity of (List) Edge-Coloring Reconfiguration Problem Peer-reviewed

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017　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. Peer-reviewed

    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

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

    DOI： 10.4230/LIPIcs.MFCS.2017.51 　

    ISSN： 1868-8969

  38. Complexity of Coloring Reconfiguration under Recolorability Constraints. Peer-reviewed

    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

    Publisher: 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 Peer-reviewed

    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

    Publisher: 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 Peer-reviewed

    Yusuke Aoki, Bjarni V. Halldorsson, Magnus M. Halldorsson, 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 Peer-reviewed

    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 Peer-reviewed

    Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E99D　(3)　598-606　2016/03

    DOI： 10.1587/transinf.2015FCP0010 　

    ISSN： 1745-1361

    eISSN： 1745-1361

  43. Algorithm for Generalized Coloring Reconfiguration Problem

    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. Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    Kei Uchizawa, Daiki Yashima, Xiao Zhou

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

    Publisher: Brown University

    DOI： 10.7155/jgaa.00387 　

    ISSN： 1526-1719

    eISSN： 1526-1719

  47. Algorithms for the Independent Feedback Vertex Set Problem Peer-reviewed

    Yuma Tamura, Takehiro Ito, Xiao Zhou

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

    DOI： 10.1587/transfun.E98.A.1179 　

    ISSN： 1745-1337

  48. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs Peer-reviewed

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

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

    DOI： 10.1587/transfun.E98.A.1168 　

    ISSN： 1745-1337

  49. The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs Peer-reviewed

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

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

    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 Peer-reviewed

    Takashi Hasegawa, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Interdisciplinary Information Sciences　21　(1)　25-35　2015

    Publisher: Tohoku University

    DOI： 10.4036/iis.2015.25 　

    ISSN： 1340-9050

    eISSN： 1347-6157

    More details Close

    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 Peer-reviewed

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    COMBINATORIAL ALGORITHMS, IWOCA 2014　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 Peer-reviewed

    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. Peer-reviewed

    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

    Publisher: Springer

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

  54. Competitive diffusion on weighted graphs Peer-reviewed

    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

    Publisher: 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 Peer-reviewed

    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 Peer-reviewed

    Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

    THEORETICAL COMPUTER SCIENCE　544　84-97　2014/08

    DOI： 10.1016/j.tcs.2014.04.011 　

    ISSN： 0304-3975

    eISSN： 1879-2294

  57. Bandwidth consecutive multicolorings of graphs Peer-reviewed

    Kazuhide Nishikawa, Takao Nishizeki, Xiao Zhou

    THEORETICAL COMPUTER SCIENCE　532　64-72　2014/05

    DOI： 10.1016/j.tcs.2013.02.015 　

    ISSN： 0304-3975

    eISSN： 1879-2294

  58. On the Minimum Caterpillar Problem in Digraphs Peer-reviewed

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E97A　(3)　848-857　2014/03

    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

    Publisher: Bangladesh Academy of Sciences (BAS)

  60. The minimum vulnerability problem on graphs Peer-reviewed

    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

    Publisher: 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. Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    Yusuke Aoki, Bjarni V. Halldorsson, Magnus M. Halldorsson, Takehiro Ito, Christian Konrad, Xiao Zhou

    COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014)　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 Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    THEORETICAL COMPUTER SCIENCE　505　74-80　2013/09

    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 Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Proceedings of the 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　17-17　2013/04/20

  69. Algorithm for the minimum caterpillar problem with terminals Peer-reviewed

    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/04/20

    ISSN： 2186-2583

    More details Close

    Suppose that each arc in a digraph D = (V, A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard even for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|).Suppose that each arc in a digraph D = (V, A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard even for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|).

  70. Algorithm for the Minimum Caterpillar Problem with Terminals

    OKADA Taku, SUZUKI Akira, ITO Takehiro, ZHOU Xiao

    情報処理学会研究報告(CD-ROM)　2013　(1)　1-7　2013/02/22

    ISSN： 2186-2583

    More details Close

    Suppose that each arc in a digraph D = (V, A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard even for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|).Suppose that each arc in a digraph D = (V, A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard even for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|).

  71. Generalized rainbow connectivity of graphs Peer-reviewed

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7748　233-244　2013

    Publisher: Springer

    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 Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7876　248-259　2013

    Publisher: Springer Verlag

    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 Peer-reviewed

    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

    Publisher: Springer

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

    ISSN： 0302-9743 1611-3349

  74. Complexity of Counting Output Patterns of Logic Circuits. Peer-reviewed

    Kei Uchizawa, Zhenghong Wang, Hiroki Morizumi, Xiao Zhou

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

    Publisher: Australian Computer Society

  75. ENERGY-EFFICIENT THRESHOLD CIRCUITS COMPUTING MOD FUNCTIONS Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　24　(1)　15-29　2013/01

    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

    Publisher: Graduate School of Information Sciences, Tohoku University

    DOI： 10.4036/iis.2012.161 　

    ISSN： 1347-6157

  77. Small grid drawings of planar graphs with balanced partition Peer-reviewed

    Xiao Zhou, Takashi Hikino, Takao Nishizeki

    JOURNAL OF COMBINATORIAL OPTIMIZATION　24　(2)　99-115　2012/08

    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 Peer-reviewed

    Takehiro Ito, Takao Nishizeki, Michael Schroeder, Takeaki Uno, Xiao Zhou

    ALGORITHMICA　62　(3-4)　823-841　2012/04

    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 Peer-reviewed

    Takehiro Ito, Kazuto Kawamura, Xiao Zhou

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E95D　(3)　737-745　2012/03

    DOI： 10.1587/transinf.E95.D.737 　

    ISSN： 0916-8532

    eISSN： 1745-1361 1611-3349

  80. Algorithms for bandwidth consecutive multicolorings of graphs Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    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

    Publisher: The Institute of Electronics, Information and Communication Engineers

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

    ISSN： 0302-9743 0304-3975

    eISSN： 1611-3349

  83. Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings Peer-reviewed

    Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E94D　(2)　190-195　2011/02

    DOI： 10.1587/transinf.E94.D.190 　

    ISSN： 1745-1361

  84. Energy-efficient threshold circuits computing Mod functions Peer-reviewed

    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/01/20

    Publisher: Australian Computer Society

  85. Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs

    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 Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011　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 Peer-reviewed

    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 Peer-reviewed

    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

    Publisher: Springer

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

    ISSN： 0302-9743

    eISSN： 1611-3349

  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/09/01

    Publisher: World Scientific Publishing 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 Peer-reviewed

    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 Peer-reviewed

    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

    Publisher: The Institute of Electronics, Information and Communication Engineers

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

    ISSN： 0913-5685

    More details Close

    Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive integer, called the supply or the demand. Every demand vertex v of T must be supplied an amount of "power," equal to the demand of v, from exactly one supply vertex through edges in T. Each edge e of T has a direction, and is assigned a positive integer which represents the cost required to delete e from T or reverse the direction of e. Then one wishes to obtain subtrees of T by deleting edges and reversing the directions of edges so that (a) each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and (b) each subtree is rooted at the supply vertex in a sense that every edge is directed away from the root. We wish to minimize the total cost to obtain such rooted subtrees from T. In the paper, we first show that this minimization problem is NP-hard, and then give a pseudo-polynomial-time algorithm to solve the problem. We finally give a fully polynomial-time approximation scheme (FPTAS) for the problem.

  93. Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings Peer-reviewed

    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 Peer-reviewed

    Xiao Zhou, Takao Nishizeki

    ALGORITHMS AND COMPUTATION, PROCEEDINGS　5878　760-770　2009

    ISSN： 0302-9743

  95. Partitioning graphs of supply and demand Peer-reviewed

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Discrete Applied Mathematics　157　(12)　2620-2633　2009

    Publisher:

    DOI： 10.1016/j.dam.2008.08.012 　

    ISSN： 0166-218X

  96. Partitioning a Weighted Tree to Subtrees of Almost Uniform Size Peer-reviewed

    Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki

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

    Publisher:

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

    ISSN： 0302-9743

    eISSN： 1611-3349

  97. 木の均一分割問題

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

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

  98. Approximability of partitioning graphs with supply and demand Peer-reviewed

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

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

    Publisher:

    DOI： 10.1016/j.jda.2008.03.002 　

    ISSN： 1570-8667

  99. Sufficient condition and algorithm for list total colorings of series-parallel graphs Peer-reviewed

    Yuki Matsuo, Xiao Zhou, Takao Nishizeki

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E90A　(5)　907-916　2007/05

    DOI： 10.1093/ietfec/e90-a.5.907 　

    ISSN： 0916-8508

    eISSN： 1745-1337

  100. Total colorings of degenerate graphs Peer-reviewed

    Shuji Isobe, Xiao Zhou, Takao Nishizeki

    COMBINATORICA　27　(2)　167-182　2007/03

    DOI： 10.1007/s00493-007-0050-5 　

    ISSN： 0209-9683

  101. Partitioning a multi-weighted graph to connected subgraphs of almost uniform size Peer-reviewed

    Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki

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

    Publisher: The Institute of Electronics, Information and Communication Engineers

    DOI： 10.1093/ietisy/e90-d.2.449 　

    ISSN： 0916-8532

    eISSN： 1745-1361

    More details Close

    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 l_i and u_i, 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 l_i and at most u_i 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 Peer-reviewed

    Takehiro Ito, Akira Kato, Xiao Zhou, Takao Nishizeki

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

    Publisher:

    DOI： 10.1016/j.jda.2006.03.020 　

    ISSN： 1570-8667

  103. Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size Peer-reviewed

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

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

    Publisher:

    DOI： 10.1016/j.jda.2005.01.005 　

    ISSN： 1570-8667

  104. Partitioning a multi-weighted graph to connected subgraphs of almost uniform size Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    Xiao Zhou, Yuki Matsuo, Takao Nishizeki

    Journal of Discrete Algorithms　3　(1)　47-60　2005/03

    Publisher:

    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

    Publisher: Springer Verlag

    DOI： 10.1007/11602613_18 　

    ISSN： 1611-3349 0302-9743

  108. Partitioning trees of supply and demand Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    Xiao Zhou, Takao Nishizeki

    Journal of Combinatorial Optimization　8　(1)　97-108　2004/03

    Publisher:

    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

    Publisher: Institute of Electronics, Information and Communication, Engineers, IEICE

    ISSN： 0916-8532

  113. Partitioning a weighted graph to connected subgraphs of almost uniform size Peer-reviewed

    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

    Publisher:

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

  114. Multicolorings of series-parallel graphs Peer-reviewed

    Xiao Zhou, Takao Nishizeki

    Algorithmica (New York)　38　(2)　271-297　2003/11

    Publisher:

    DOI： 10.1007/s00453-003-1060-3 　

    ISSN： 0178-4617

    eISSN： 1432-0541

  115. List edge-colorings of series-parallel graphs Peer-reviewed

    T Fujino, Zhou, X, T Nishizeki

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

    ISSN： 0916-8508

    eISSN： 1745-1337

  116. Linear algorithm for finding list edge-colorings of series-parallel graphs Peer-reviewed

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

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E86D　(2)　186-190　2003/02

    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

    Publisher: Springer Verlag

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

    ISSN： 1611-3349 0302-9743

  118. Algorithms for multicolorings of partial k-trees Peer-reviewed

    Takehiro Ito, Takao Nishizeki, Xiao Zhou

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

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0916-8532

    More details Close

    Let each vertex ★ of a graph G have a positive integer weight ★(★). Then a multicoloring of G is to assign each vertex ★ a set of ★(★) 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.

  119. Algorithms for the multicolorings of partial k-trees Peer-reviewed

    Takehiro Ito, Takao Nishizeki, Xiao Zhou

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

    Publisher:

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

  120. Partitioning trees of supply and demand Peer-reviewed

    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

    Publisher: 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

    Publisher: 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 Peer-reviewed

    Zhou, X, T Nishizeki

    ALGORITHMS AND COMPUTATION, PROCEEDINGS　2223　514-524　2001

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

    ISSN： 0302-9743

  124. A linear algorithm for finding [g, f]-colorings of partial k-trees Peer-reviewed

    Zhou, X, K Fuse, T Nishizeki

    ALGORITHMICA　27　(3-4)　227-243　2000/07

    DOI： 10.1007/s004530010017 　

    ISSN： 0178-4617

  125. Algorithms for generalized vertex-rankings of partial k-trees Peer-reviewed

    MA Kashem, Zhou, X, T Nishizeki

    THEORETICAL COMPUTER SCIENCE　240　(2)　407-427　2000/06

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

    ISSN： 0304-3975

  126. Graph coloring algorithms Peer-reviewed

    Zhou, X, T Nishizeki

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS　E83D　(3)　407-417　2000/03

    ISSN： 0916-8532

  127. Finding independent spanning trees in partial k-trees

    Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　1969　168-179　2000

    Publisher: Springer Verlag

    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 Peer-reviewed

    Xiao Zhou, Takao Nishizeki

    Journal of Combinatorial Theory. Series B　75　(2)　270-287　1999/03

    Publisher:

    DOI： 10.1006/jctb.1998.1883 　

    ISSN： 0095-8956

  129. A linear algorithm for finding total colorings of partial fc-trees Peer-reviewed

    Shuji Isobe, Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　1741　347-356　1999

    Publisher: Springer Verlag

    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

    M. A. Kashem, Xiao Zhou, T. Nishizeki

    3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997　105-111　1997

    Publisher: Institute of Electrical and Electronics Engineers Inc.

    DOI： 10.1109/ISPAN.1997.645078 　

  131. Generalized vertex-rankings of partial k-trees

    Md Abul Kashem, Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　1276　212-221　1997

    Publisher: Springer Verlag

    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

    Publisher:

    DOI： 10.1006/jagm.1996.0008 　

    ISSN： 0196-6774

  135. OPTIMAL PARALLEL ALGORITHMS FOR EDGE-COLORING PARTIAL K-TREES WITH BOUNDED DEGREES Peer-reviewed

    ZHOU, X, T NISHIZEKI

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

    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/01/22

    Publisher: Association for Computing Machinery

  137. Edge-coloring algorithms Invited

    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 Peer-reviewed

    Xiao Zhou, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　959　223-228　1995

    Publisher: Springer Verlag

    DOI： 10.1007/BFb0030836 　

    ISSN： 1611-3349 0302-9743

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

    Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　824　359-369　1994

    Publisher: Springer Verlag

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

    ISSN： 1611-3349 0302-9743

  140. An efficient algorithm for edge-coloring series parallel multigraphs Peer-reviewed

    X. Zhou, S. Nakano, H. Suzuki, T. Nishizeki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　583　516-529　1992

    Publisher: Springer Verlag

    DOI： 10.1007/BFb0023853 　

    ISSN： 1611-3349 0302-9743

Show all ︎Show first 5

Misc. 78

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

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

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

  2. Independent Set and Vertex Cover Reconfiguration Under Extended Rules

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

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

  3. Shortest Path Reconfiguration with Relaxed Constraints

    DOMON Naoki, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

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

  4. Algorithms for Weighted Target Set Selection

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

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

    ISSN： 1349-144X

  5. The Independent Set Reconfiguration Problem Based on Relaxation of Reconfiguration Rules

    菅達皓, 鈴木顕, 田村祐馬, 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/07/18

    Publisher: ACM

    DOI： 10.1145/3539618.3591635 　 10.1145/3626772.3657799_references_DOI_NPXFggGzY6RhT3VfeHMmhqzyCbI 　

  7. On the Problems of Finding Paths to Avoid Ordered Forbidden Transitions Based on Graph Structure

    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/06/28

    Publisher: 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

    More details Close

    <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/09

    Publisher: 東京 : 電気学会

  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/07/01

    Publisher: 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/07

    Publisher: International Joint Conferences on Artificial Intelligence Organization

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

    More details Close

    <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: システム数理と応用

    117　(301)　23-27　2017/11/16

    Publisher: 電子情報通信学会

    ISSN： 0913-5685

  13. Energy-efficient Threshold Circuits Computing Generalized Symmetric Functions (Frontiers of Theoretical Computer Science)

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

    RIMS Kokyuroku　2040　(2040)　21-26　2017/07

    Publisher: 京都大学数理解析研究所

    ISSN： 1880-2818

  14. Reachability between Steiner Trees in a Graph

    116　(116)　109-113　2016/06/24

    Publisher: 電子情報通信学会

    ISSN： 0913-5685

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

    Hatanaka Tatsuhiko, Ito Takehiro, Zhou Xiao

    Proceedings of the IEICE General Conference　2016　(1)　"S-8"-"S-9"　2016/03/01

    Publisher: The Institute of Electronics, Information and Communication Engineers

  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

    Publisher: 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

    More details Close

    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. Reconfiguration of List Colorings in a Graph (Theoretical Foundations of Computing)

    HATANAKA Tatsuhiko, ITO Takehiro, ZHOU Xiao

    IEICE technical report. Theoretical foundations of Computing　114　(238)　19-24　2014/10/08

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we give precise analyses of the problem with respect to pathwidth. We first show that the problem remains PSPACE-complete even for graphs with pathwidth two. In contrast, we then give a polynomial-time algorithm to solve the problem for graphs with pathwidth one.

  18. Algorithms for the Minimum Vulnerability Problem (Theoretical Foundations of Computing)

    AOKI Yusuke, HALLDORSSON Bjarni V., HALLDORSSON Magnus M., ITO Takehiro, KONRAD Christian, ZHOU Xiao

    IEICE technical report. Theoretical foundations of Computing　114　(238)　9-15　2014/10/08

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    Suppose that each edge e of an undirected graph G is associated with three nonnegative integers cost(e), vul(e) and cap(e), called the cost, vulnerability and capacity of e, respectively. Then, we consider the problem of finding k paths in G between two prescribed vertices with the minimum total cost; each edge e can be shared without any cost by at most vul(e) paths, and can be shared by more than vul(e) paths if we pay cost(e), but cannot be shared by more than cap(e) paths even if we pay the cost of e. This problem generalizes the disjoint path problem, the minimum shared edges problem and the minimum edge cost flow problem for undirected graphs, and it is known to be NP-hard. In this paper, we study the problem from the viewpoint of specific graph classes, and give three results. We first show that the problem is NP-hard even for bipartite series-parallel graphs, and for threshold graphs. We then give a pseudo-polynomial-time algorithm for bounded treewidth graphs. Finally, we give a fixed-parameter algorithm for chordal graphs when parameterized by the number k of required paths.

  19. The Independent Feedback Vertex Set Problem

    TAMURA Yuma, ITO Takehiro, ZHOU Xiao

    IEICE technical report. Theoretical foundations of Computing　114　(80)　13-18　2014/06/13

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    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.

  20. The Independent Feedback Vertex Set Problem

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    IPSJ SIG Notes　2014　(3)　1-6　2014/06/06

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    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. The Server Supply-Assignment Problem on Graphs under a Given Routing Table (New Streams of Computation Theory and Algorithms)

    Oohino Hajime, Ito Takehiro, Suzuki Akira, Uchizawa Kei, Zhou Xiao

    RIMS Kokyuroku　1894　41-44　2014/05

    Publisher: Kyoto University

    ISSN： 1880-2818

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

    Suzuki Akira, Uchizawa Kei, Zhou Xiao

    RIMS Kokyuroku　1849　133-134　2013/08

    Publisher: Kyoto University

    ISSN： 1880-2818

  23. Threshold Circuits to Calculate $P^n_D$ Function (New Trends in Theoretical Computer Science)

    Yashima Daiki, Uchizawa Kei, Zhou Xiao

    RIMS Kokyuroku　1849　127-132　2013/08

    Publisher: Kyoto University

    ISSN： 1880-2818

  24. Complexity of Counting Output Patterns of Logic Circuit

    UCHIZAWA Hiroshi, Zhenghong Wang, Hiroki Morizumi, Xiao Zhou

    Journal of the Japanese Society of Irrigation,Drainages and Reclamation Engineering　2013　(15)　1-6　2013/05/10

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0369-5123

    More details Close

    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

    Ito Takehiro, Kawamura Kazuto, Ono Hirotaka, Zhou Xiao

    IEICE technical report. Theoretical foundations of Computing　112　(340)　33-40　2012/12/10

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    Abstract For an integer κ≧O, suppose that each vertex v of a graph G has a set C(ν)⊆{O,1,...,κ} 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 κ≧6. In contrast, we then show that the problem can be solved in linear time for general graphs if κ≦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.

  26. Algorithms for Bandwidth Consecutive Multicolorings of Graphs

    NISIKAWA Kazuhide, NISHIZEKI Takao, ZHOU Xiao

    IEICE technical report. Theoretical foundations of Computing　111　(360)　17-24　2011/12/16

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    Let G be a simple graph in which each vertex v has a positive integer weight b(v) and each edge (v, w) has a nonnegative integer weight b(v, w). A bandwidth consecutive multicoloring of G assigns each vertex v a specified number b(v) of consecutive positive integers so that, for each edge (v, w), all integers assigned to vertex v differ from all integers assigned to vertex w by more than b(v, w). The maximum integer assigned to a vertex is called the span of the coloring. In the paper, we first investigate fundamental properties of such a coloring. We then obtain a pseudo polynomial-time exact algorithm and a fully polynomial-time approximation scheme for the problem of finding such a coloring of a given graph with the minimum span for the case G is a series-parallel graph. We finally extend the results to the case G is a partial k-tree, that is, G has a bounded tree-width.

  27. Reconfiguration of Vertex Covers in Trees and Cacti

    NOOKA Hiroyuki, ITO Takehiro, ZHOU Xiao

    IEICE technical report. Theoretical foundations of Computing　111　(360)　25-32　2011/12/16

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    We study the problem of reconfiguring a vertex cover of a graph G into another vertex cover via vertex covers of G, each of which results from the previous one by deleting or adding a single vertex, without ever going through a vertex cover of size more than k, for a given integer threshold k. This decision problem is known to be PSPACE-complete for planar graphs. In this paper, we first give a sufficient condition on the threshold k for which there always exists a reconfiguration between any two vertex covers for cacti. We then give a linear-time algorithm for trees to compute the minimum threshold k for which there exists a reconfiguration between two given vertex covers.

  28. Reconfiguration of List Edge-Colorings in a Tree

    KAWAMURA Kazuto, ITO Takehiro, ZHOU Xiao

    IEICE technical report　110　(464)　53-60　2011/03/02

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kaminski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with n vertices via O(n^2) recoloring steps. We remark that the upper bound O(n^2) on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires Ω(n^2) recoloring steps.

  29. DS-1-4 Energy and Fan-in of Threshold Circuits Computing Mod Functions

    Suzuki Akira, Uchizawa Kei, Xiao Zhou

    Proceedings of the IEICE General Conference　2011　(1)　"S-7"-"S-8"　2011/02/28

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 1349-1369

    More details Close

    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

    2011　(4)　1-8　2011/02/28

    Publisher: 情報処理学会

    ISSN： 2186-2583

  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

    Publisher: 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

    More details Close

    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. Energy-Efficient Threshold Circuits Computing Mod Functions

    SUZUKI Akira, UCHIZAWA Kei, ZHOU Xiao

    IEICE technical report　110　(325)　7-13　2010/11/26

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    We prove that the modulus function MOD_m of n variables can be computed by a threshold circuit C of energy e and size s=O(e(n/m)^<1/(e-1)>) for any integer e≧2, where the energy e is defined to be the maximum number of gates outputting "1" over all inputs to C, and the size s to be the number of gates in C. Our upper bound on the size s almost matches the known lower bound s=Ω(e(n/m)^<1/e)).

  33. Minimum Cost Edge-Colorings of Trees Can be Reduced to Matchings

    ITO Takehiro, SAKAMOTO Naoki, ZHOU Xiao, NISHIZEKI Takao

    IEICE technical report　110　(214)　9-15　2010/09/22

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    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 ω(f) of an edge-coloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if ω(f) 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(n^<1.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.

  34. Small Grid Drawings of Planar Graphs with Balanced Bipartition

    ZHOU Xiao, HIKINO Takashi, NISHIZEKI Takao

    IEICE technical report　109　(235)　9-15　2009/10/09

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It has been known that every planar graph G of n vertices has a grid drawing on an (n-2)×(n-2) integer grid and such a drawing can be found in linear time. In this paper we show that if a planar graph G has a balanced bipartition then G has a grid drawing with small grid area. More precisely, if a separation pair bipartitions G into two edge-disjoint subgraphs G_1 and G_2, then G has a grid drawing on a W×H grid such that both the width W and height H are smaller than the larger number of vertices in G_1 and in G_2. In particular, we show that every series-parallel graph has a grid drawing on a (2n/3)×(2n/3) grid and such a drawing can be found in linear time.

  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

    Publisher: Elsevier BV

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

    ISSN： 0375-9601

  36. A-026 Grid Drawings of Planar Graphs using Bipartition

    Hikino Takashi, Zhou Xiao, Nishizeki Takao

    8　(1)　309-310　2009/08/20

    Publisher: Forum on Information Technology

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

    Zhou Xiao, Nishizeki Takao

    8　(1)　311-312　2009/08/20

    Publisher: Forum on Information Technology

    More details Close

    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/08

    ISSN： 1884-0930

  39. Convex Drawings of Internally Triconnected Plane Graphs on O (n2) Grids

    ZHOU XIAO, NISHIZEKI TAKAO

    2009　(2)　1-8　2009/07/14

    Publisher: 情報処理学会

    ISSN： 0919-6072

  40. Convex Grid Drawings of Subdivisions of Triconnected Plane Graphs

    ZHOU Xiao, ABE Takashi, NISHIZEKI Takao

    IEICE technical report　108　(237)　77-84　2008/10/03

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    In a convex grid drawing of a plane graph, every vertex is located at a grid point and every facial cycle is drawn as a convex polygon. If a plane graph is triconnected and has n vertices, then it has a convex grid drawing in an (n-1)×(n-1) integer grid and hence the area of the drawing is O(n^2). If a plane graph has a vertex of degree two, then it is not triconnected but may have a convex grid drawing, whose area is not necessarily O(n^2). In the paper, we deal with a subdivision G of a triconnected plane graph G', which is obtained from G' by inserting vertices of degree two into edges, and give a linear algorithm to find a convex grid drawing of G in a grid of O(n^3) area.

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

    SIAM journal on discrete mathematics　22　(4)　1570-1604　2008

    Publisher: Society for Industrial and Applied Mathematics

    DOI： 10.1137/060667621 　

    ISSN： 0895-4801

    eISSN： 1095-7146

  42. Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends

    ZHOU Xiao, NISHIZEKI Takao

    IEICE technical report　105　(343)　7-14　2005/10/18

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    In an orthogonal drawing of a planar graph G, each vertex is drawn as a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. A bend is a point where an edge changes its direction. A drawing of G is called an optimal orthogonal drawing if the number of bends is minimum among all orthogonal drawings of G. In this paper we give an algorithm to find an optimal orthogonal drawing of any given series-parallel graph of the maximum degree at most three. Our algorithm takes linear time, while the previously known best algorithm takes cubic time. Furthermore, our algorithm is much simpler than the previous one. We also obtain a best possible upper bound on the number of bends in an optimal drawing.

  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

    Publisher: IEEE Comput. Soc. Press

    DOI： 10.1109/ispan.1994.367150 　

    More details Close

    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 Algorithm for Finding List Edge-Colorings of Series-Parallel Graphs

    Fujino Tomoya, Zhou Xiao, Nishizeki Takao

    1　21-22　2002/09/13

    Publisher: Forum on Information Technology

  45. A-37 List Total-Colorings of Series-Parallel Graphs

    2002　(1)　73-74　2002/09/13

    Publisher: Forum on Information Technology

  46. Algorithms for Tree Partitioning

    KABAKURA Masanori, ZHOU Xiao, NISHIZEKI Takao

    IEICE technical report. Theoretical foundations of Computing　101　(707)　33-40　2002/03/04

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    Let G=(V_d,V_8;E) be a graph with vertex sets, which is partitioned into two subsets V_d and V_8. Let each vertex v ∈ V_d have a positive real number demand d(v), and each vertex u ∈ V_s have a positive real number supply s(u). We find a partition of G by removing some edges such that each connected component has at most one supply vertex in V_s, and for each connected component C with a supply vertex the amount of demand of vertices in C is at most its supply. In this paper, we give a linear time algorithm to find a partition of tree such that each connected component has exactly one supply vertex, and an O(m^2_sn)-time algorithm to find a partition of tree such that the amount of demands of vertices of connected components, which contains a supply vertex, is maximum, where n is the number of vertices and m_s is the maximum supply.

  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

    Publisher: 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

    More details Close

    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. Efficient Algorithms for the Weighted Coloring of Series-Parallel Graphs

    ZHOU Xiao, NISHIZEKI Takao

    IEICE technical report. Theoretical foundations of Computing　101　(376)　1-8　2001/10/12

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    Let G be a weighted graph such that each vertex υ has a positive integer weight ω(υ). A weighted coloring of G is to assign a set of ω(υ) colors to each vertex υ so that any two adjacent vertices receive disjoint sets of colors. This paper gives an efficient algorithm to find the minimum number of colors required for a weighted coloring of a given series-parallel graph G in time Ο(nω_max), where n is the number of vertices and ω_max is the maximum vertex-weight of G.

  49. Algorithm for the List Edge-Coloring of Series-Parallel Graphs

    FUJINO Tomoya, ZHOU Xiao, NISHIZEKI Takao

    IEICE technical report. Theoretical foundations of Computing　101　(376)　9-14　2001/10/12

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). In this paper, we prove that any series-parallel simple graph G has an L-edge-coloring if |L(e)|&gnE;max{4, d(ι').d(μ')} for each edge e = ι'u', where d(ι') and d(u') are the degrees of the ends ι' and u' of e, respectively. We furthermore prove that, in particular when the maximum degree of G is at most three, G has an L-edge-coloring if |L(e)|&gnE;max{3.d(ι').d(u')}. Our proof immediately yields an efficient algorithm for finding an L-edge-coloring of series-parallel graphs.

  50. Total Colorings of Degenerated Graphs

    Takao Nishizeki, Shuji Isobe, Xiao Zhou

    Combinatorica　27　167-182　2001/01/01

    Publisher: Springer Berlin Heidelberg

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

    ISSN： 0209-9683

    eISSN： 1439-6912

    More details Close

    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. Finding Independent Spanning Trees in Partial k-Trees

    ZHOU Xiao, NISHIZEKI Takao

    IEICE technical report. Theoretical foundations of Computing　100　(402)　9-16　2000/10/20

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    Spanning trees rooted at a vertex r of a graph G are independent if, for each vertex v in G, all the paths connecting v and r in the trees are pairwise internally disjoint. In this paper we give a linear-time algorithm to find the maximum number of independent spanning trees rooted at any given vertex r in partial k-trees G, that is, graphs G with tree-width bounded by a constant k.

  52. Total Colorings of Degenerated Graphs

    ISOBE Shuji, ZHOU Xiao, NISHIZEKI Takao

    IEICE technical report. Theoretical foundations of Computing　100　(402)　1-8　2000/10/20

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    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. A graph G is s-degenerated if G can be reduced to a trivial graph by successive removal of vertices with degree &le; s. We prove that an s-degenerated graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ &ge; 4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a linear-time algorithm to find a total coloring of partial k-trees, i.e., graphs with bounded tree-width, with the minimum number of colors.

  53. Generalized Vertex-Colorings of Partial κ-Trees

    ZHOU Xiao, KANARI Yasuaki, NISHIZEKI Takao

    IEICE Trans. Fundamentals, A　83　(4)　671-678　2000/04/25

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0916-8508

    More details Close

    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. A Linear Algorithm for Finding Total Colorings of Partial $k$-Trees (Algorithm Engineering as a New Paradigm)

    Isobe Shuji, Xiao Zhou, Nishizeki Takao

    RIMS Kokyuroku　1120　33-40　1999/12

    Publisher: Kyoto University

    ISSN： 1880-2818

  55. A polynomial-time algorithm for finding total colorings of partial k-trees

    ISOBE S.

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

    Publisher: World Scientific Pub Co Pte Lt

    DOI： 10.1142/S0129054199000137 　

    ISSN： 0129-0541

    eISSN： 1793-6373

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

    ZHOU X, TAMURA S, NISHIZEKI T

    Algorithmica　26　(1)　3-30　1999

    Publisher: Springer Science and Business Media LLC

    DOI： 10.1007/s004539910002 　

    ISSN： 0178-4617

    eISSN： 1432-0541

    More details Close

    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. A Polynomial-Time Algorithm for Finding l-Vertex-Colorings of Partial k-Trees

    57　139-140　1998/10/05

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

    ISOBE Shuji, ZHOU Xiao, NISHIZEKI Takao

    IPSJ SIG Notes　1998　(62)　33-40　1998/07/22

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    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. The Edge - Disjoint Paths Problem is NP - Complete for Partial k - Trees

    ZHOU Xiao, NISHIZEKI Takao

    IPSJ SIG Notes　1998　(41)　25-32　1998/05/20

    Publisher: Information Processing Society of Japan (IPSJ)

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

    ISSN： 0919-6072

    More details Close

    Many combinatorial problems are NP-complete for general graphs, but are not NP-complete for partial κ-trees(graphs of treewidth bounded by a constant κ)and can be efficiently solved in polynomial time or mostly in linear time for partial κ-trees.On the other hand, very few problems on unweighted graphs are known to be NP-complete for partial κ-trees with bounded κ. 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 κ-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 κ-trees with some bounded κ&ge;2 although the problem is trivially solvable for trees.

  60. Generalized Edge-Rankings of Trees

    ZHOU Xiao, KASHEM Md. Abul, NISHIZEKI Takao

    IEICE Transactions, A　81　(2)　310-320　1998/02/25

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0916-8508

    More details Close

    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. Generalized Vertex - Rankings of Partial k - Trees

    MD. ABUL Kashem, ZHOU Xiao, NISHIZEKI Takao

    IPSJ SIG Notes　1997　(26)　27-34　1997/03/14

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G With integers 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 κ-tree using the minimum number of ranks for any positive integer c and any bounded integer κ. 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

    Zhou, X, MA Kashem, T Nishizeki

    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE　1197　390-404　1997

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

    ISSN： 0302-9743

  64. An Algorithm for Finding [g,f] - Colorings of Partial k - Trees

    ZHOU Xiao, FUSE Kazuki, NISHIZEKI Takao

    IPSJ SIG Notes　1996　(100)　73-80　1996/10/17

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    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. A Polynomial algorithm for finding [g,f]-colorings of partial k-trees

    53　359-360　1996/09/04

  66. Finding Edge - Disjoint Paths in Partial k - Trees

    ZHOU Xiao, TAMURA Syurei, NISHIZEKI Takao

    IPSJ SIG Notes　1996　(67)　65-72　1996/07/24

    Publisher: Information Processing Society of Japan (IPSJ)

    DOI： 10.1007/bfb0009496 　

    ISSN： 0919-6072

    More details Close

    For a given graph G and p pairs (s_i, t_i), 1&le;i&le;p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P_i, 1&le;i&le;p, connecting s 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&le;i&le;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/03/11

    Publisher: 一般社団法人電子情報通信学会

    More details Close

    本文では部分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/01

    Publisher: Elsevier BV

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

    ISSN： 0020-0190

    More details Close

    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. Generalized Edge - Rankings of Trees

    ZHOU Xiao, KASHEM Md. Abul, NISHIZEKI Takao

    IPSJ SIG Notes　1995　(71)　73-80　1995/07/20

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    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^2 log Δ), where n is the number of vertices in T and Δ is the maximum vertex-degree of T.

  70. Algorithms for Finding f - Colorings of Partial k - Trees

    ZHOU Xiao, NISHIZEKI Takao

    IPSJ SIG Notes　1995　(71)　97-104　1995/07/20

    Publisher: Information Processing Society of Japan (IPSJ)

    DOI： 10.1007/bfb0015439 　

    ISSN： 0919-6072

    More details Close

    In an ordinary edge-coloring of a graph G = (V,E) each color appears at each vertex v ∈ V at most once. An f-coloring is a generalized edge-coloring in which each color appears at each vertex v ∈ V at most f(v) times, where f(v) is a positive integer assigned to v. 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(v)'s are bounded.

  71. Generalized Rankings of Trees

    1994　(100)　87-94　1994/11/18

  72. An Efficient Algorithm for Edge - Ranking Trees

    Zhou Xiao, Nishizeki Takao

    IPSJ SIG Notes　1994　(69)　9-16　1994/07/22

    Publisher: Information Processing Society of Japan (IPSJ)

    DOI： 10.1007/bfb0049402 　

    ISSN： 0919-6072

    More details Close

    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^3 log n) 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 I(n^2) time.

  73. Edge - Coloring and f - Coloring for Various Classes of Graphs

    Zhou Xiao, Nishizeki Takao

    IPSJ SIG Notes　1994　(26)　9-16　1994/03/17

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    In an ordinary edge-coloring of a graph G=(V, E) each color appears at each vertex υ ∈ V at most once. An &fnof;-coloring is a generalized coloring in which each color appears at each vertex υ ∈ V at most &fnof;(υ) times. This paper gives efficient sequential and parallel algorithms which find ordinary edge-colorings and &fnof;-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/01/01

    Publisher: Springer Berlin Heidelberg

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

    eISSN： 1526-1719

    More details Close

    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. A Parallel Algorithm for Edge - Coloring Partial k - Trees

    Zhou Xiao, Nakano Shin-ichi, Nishizeki Takao

    IPSJ SIG Notes　1993　(48)　25-32　1993/05/28

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    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 κ-trees. The edge-coloring problem is one of a few combinatorial problems for which no NC algorithms have been obtained for partial κ-trees. This paper gives a first NC parallel algorithm which finds an optimal edge-coloring of a given partial κ-tree.

  76. A Linear Algorithm for Edge -Coloring Partial k- Trees

    1993　(24)　89-96　1993/03/18

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

    45　57-58　1992/09/28

  78. A Linear Algorithm for Edge -Coloring Series- Parallel Multigraphs

    1992　(78)　49-56　1992/09/25

Show all ︎Show first 5

Research Projects 17

  1. The Ridesharing Problem of Graphs and Its Applications

    Zhou Xiao

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2019/04/01 - 2022/03/31

    More details Close

    The purpose of this research is to construct an efficient algorithm design theory for solving the ride-sharing problem of graphs, and to study a route formulation methodology that can be applied to the transportation of emergency relief supplies in the event of a large-scale disaster. The results of the research include the theoretical development of graphs, especially those of trees and graphs with small tree widths, and the efficiency of algorithms. I think that the algorithm developed in this research can be applied to many combination problems in trees and cographs, etc., and can contribute to the development of efficient algorithms, polynomial time algorithms, and FPT algorithms. We have published 5 academic papers summarizing the results obtained in this research, which can be highly evaluated.

  2. Research on Design Method of Graph Algorithm based on Tree Structure

    Zhou Xiao

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2016/04/01 - 2019/03/31

    More details Close

    The results obtained in this research are theoretical development of efficient algorithms for graphs with small tree-widths. The tree-width of a graph is the maximum value obtained by subtracting 1 from the number of vertices in nodes of its tree-decomposition. The graph of tree-width 1 is a forest, and the graph of tree-width 2 is series-parallel. In this research, in particular, we succeeded in researching and developing efficient algorithms for solving many combinatoric optimal problems by introducing graph division and clever dynamic programming to a graph having a tree structure. In particular, the algorithms developed in this research are applicable to many combinatoric problems, and we have published 12 academic papers summarizing the results obtained in this research, which can be highly appreciated.

  3. Efficient Algorithms for Partitionings, Colorings and Drawings of Graphs and their Applications

    NISHIZEKI Takao, ZHOU Xiao, ITO Takehiro, UCHIZAWA Kei

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    2009/04/01 - 2014/03/31

    More details Close

    This research develops efficient algorithms for the partitioning, coloring and drawing problems of graphs, and applies them to practical problems in real world. One of the representative results is an algorithm for the fairest connected partition problem. It partitions a weighted graph G to a specified number of connected subgraphs by deleting edges from G so that the difference between the maximum sum of weights in a subgraph and the minimum one is as small as possible.

  4. Study on a Design Method of Graph Partition Algorithm and Its Applications

    ZHOU Xiao

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2011 - 2013

    More details Close

    Result of this research includes the theoretical development and efficient algorithms to solve the partition problem for graphs with small tree-width, such as trees, series-parallel graphs and partial k-trees. We modeled power delivery networks by the graph with demand vertices and supply vertices, and find an electric power transmission such that the total of the demands is maximum. In this research, we show that the problem is NP-hard even for trees. For partial k-trees, we give a pseudo polynomial-time algorithm to solve it by introducing a clever partition of graphs and dynamic programming technique. These results are appreciated and one of them won the best paper award of FAW-AAIM 2012.

  5. Design Theory of Algorithms for Partial k-Trees

    ZHOU Xiao

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2007 - 2009

    More details Close

    In this research, I succeeded to solve some combination optimization and build the methodology that could generate efficient algorithm to solve those problems automatically. Furthermore, for a small k, say one (trees) or two (series-parallel graphs), it succeeded to develop polynomial-time algorithm for solving many combination problem. Inspection of effectiveness of the technique was possible theoretically. In this research, I have published 8 journal papers and 3 international conference papers. As a result of having been provided, I give a design theory of linear-time algorithms. Its impact in a field of a linear-time algorithm theory is very important.

  6. Graph Drawing Algorithms and Applications to VLSI Designs

    NISHIZEKI Takao, XIAO Zhou, ITO Takehiro, UCHIZAWA Kei

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2007 - 2008

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

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

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 特定領域研究

    Institution: 東北大学

    2004 - 2007

    More details Close

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

  8. Unified Methodology for Designing Efficient Algorithms

    NISHIZEKI Takao, ZHOU Xiao, ITO Takehiro

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2005 - 2006

    More details Close

    In this project, we consider the coloring problem, the disjoint path problem and the drawing problem for structured graphs such as trees, series-parallel graphs and partial k-trees, and succeeded in obtaining efficient algorithms for these classes of graphs. We also establish the foundation for the unified methodology of designing efficient algorithms for structured graphs. For trees, we obtain a fully polynomial-time approximation scheme (FPTAS) for the partitioning problem of trees having supply and demand. For series-parallel graphs, we first obtain a sufficient condition for the existence of a list total coloring, and then give a linear-time algorithm to find a list total coloring. For partial k-trees, we succeeded in obtaining three algorithms : the first is a linear-time algorithm for the total coloring problem ; the second is a pseudo-polynomial-time algorithm for the uniform partitioning problem ; and the third is a pseudo-polynomial-time algorithm for the partitioning problem on graphs with supply and demand. Concerning graph drawing, we obtain a linear-time algorithm to find an orthogonal drawing of series-parallel graphs with the minimum number of bends, and give a graph decomposition applicable to a convex drawing. In conclusion, we succeeded in designing efficient algorithms for various problems, and laid the foundation of unified methodology to design efficient algorithms for combinatorial problems, especially for the partition problems to edge-disjoint subgraphs. These results are published in seven journal papers and five proceedings papers of international conferences.

  9. The Research for Finding Algorithms to Solve Some Combination Problems on Partial k-Trees

    ZHOU Xiao, NISHIZEKI Takao

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2004 - 2006

    More details Close

    In a field of a computational complexity theory and algorithm theory, various combination problems on graphs have been studied. It is known that the most of such problems, including a lot of practical problems, are NP-hard. On the other hand, it is known that some of these problems can be solved in polynomial time for restricted classes of graphs, named partial k-trees. However, in my best knowledge there exist polynomial-time algorithms for solving some particular problems on partial k-trees and no general methods for it. In this research, I investigated existing algorithms for partial k-trees and find some algorithms to solve some combination problems of a part k tree including a [g, f]-coloring algorithm, a multiple coloring algorithm, a cost coloring algorithm, etc. It succeeded to find some conditions for solving some combination optimization and building the methodology that could generate efficient algorithm to solve those problems automatically. Furthermore, for a small k, say one (trees) or two (series-parallel graphs), it succeeded to develop polynomial-time algorithm for solving cost coloring problem, multiple coloring problem, etc. Inspection of effectiveness of the technique was possible theoretically. In this research, I have published 17 journal papers and 20 international conference papers. As a result of having been provided, I give many linear-time algorithms. Its impact in a field of a linear-time algorithm theory is very big.

  10. Research on algorithms and theory of graph drawings

    NISHIZEKI Takao, ZHOU Xiao, RAHMAN Md.Saidur, MIURA Kazuyuki, ASANO Yasuhito

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2003 - 2004

    More details Close

    In a rectangular drawing, all the faces including the outer face must be drawn as rectangles. Thomassen gave a necessary and sufficient condition for a plane graph to have a rectangular drawing. However, the condition applies only for a graph of maximum degree Δ three. In this research, we first introduce a new drawing style called an inner rectangular drawing, in which all inner faces must be rectangles but the outer face can be an axis-parallel polygon like an L-shape or T-shape polygon. We then give a necessary and sufficient condition for a plane graph to have an inner rectangular drawing not only for Δ≦3 but also for general Δ. We also give an efficient algorithm to find an inner rectangular drawing. These results solve an open problem for these thirty years, and have many practical applications.v We propose another new drawing style called a box-rectangular drawing, which is a generalization of a rectangular drawing and a box-orthogonal drawing. We then obtain an efficient algorithm to find a box-rectangular drawing. The algorithm takes time linear in the number of vertices in a given graph, and hence the time complexity is optimal, and cannot be improved any more. A conventional method for designing a VLSI layout uses a rectangular drawing, and may produce a layout in which some modules would be adjacent although they should not be adjacent. A new method using our algorithm produces a layout without such an unwanted adjacency of modules. For other drawing styles such as a straight-line drawing, a convex drawing, and a rectangle-of-influence drawing, we obtain new efficient algorithms for finding drawings of small area. In particular, we succeeded in obtaining an algorithm to find a straight-line drawing of a four-connected plane graph. The algorithm requires one quarter of the area required by the known algorithm.

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

    周 暁

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 若手研究(B)

    Institution: 東北大学

    2001 - 2002

    More details Close

    今年度は効率のよい通信スケジューリングのアルゴリズムをグラフアルゴリズム、特にリスト辺彩色や多重彩色アルゴリズムを応用して研究開発を行なった。リスト辺彩色や多重彩色問題は辺彩色や点彩色問題の一般化であり、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. A Study on Efficient Graph Algprithms and their Evaluation

    NISHIZEKI Takao, MIURA Kazuyuki, ZHOU Xiao

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2001 - 2002

    More details Close

    In this project, we first deal with the coloring, total coloring, multicoloring, list edge-coloring, edge-disjoint paths, and partitioning problems on structured graphs such as trees, seriesparallel graphs, partial κ-trees and degenerate graphs, and design and analyse efficient algorithms for these problems. We then investigate the drawing problems of plane graphs. For trees, we obtain an algorithm to solve the cost edgecoloring problem in time ο(nΔ^2), and give a pseudo-polynomial time algorithm and FPTAS for the partitioning problem. For series-parallel graphs, we obtain algorithms for the weighted coloring, multicoloring, list edge-coloring problems. We also succeed in proving the NP-completeness of the edge-disjoint paths problem on series-parallel graphs. For partial κ-trees, we give an algorithm to solve the multicoloring problem in time polynomial in the number n of vertices and in the maximum weight W. For degenerate graphs, we obtain an efficient algorithm for the total coloring problem. For planar graphs, we give an algorithm to solve the non-crossing Steiner forest problem under a 2-face condition in time ο(n log n). Concerning the graph drawing problem, we first obtain efficient algorithms to find a straight-line drawing of 4-connected plane graphs on a small grid, a rectangular drawing without designating corners, and an orthogonal drawing with the minimum number of bends, and then give a characterization of plane graphs having inner rectangular drawings.

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

    周 暁

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 奨励研究(A)

    Institution: 東北大学

    1999 - 2000

    More details Close

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

  14. Algorithm Engineering for Structural Graphs

    NISHIZEKI Takao, ZHOU Xiao

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    1999 - 2000

    More details Close

    This project aimed to establish "Paradigm for Designing Efficient Algorithms on Structured Graphs." We approached the project by taking up the unresolved problems of trees, series-parallel graphs, partial κ-trees in structured graphs, and succeeded in finding the efficient algorithms for colorings, disjoint paths, graph drawings, as follows : -gave 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 ; -gave an algorithm for finding a noncrossing Steiner forest in O(n log n) time in the case that all terminals are on the outer face of a biconnected plane graph G ; -presented 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.This algorithm is fater than the best known for the case c=1 : -proved that the edge-disjoint paths problem is NP-complete for partial κ-trees with some bounded κ, say κ=3, although the problem is trivially solvable for trees ; -gave a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time O(n7/4 √<logn>) for any plane graph of n vertices. Since 1987 we have devoted ourselves to develop "Paradigm for Designing Efficient Algorithms on Structured Graphs" and succeeded in giving the best possible algorithms for many difficult problems. We are confident that we made a great contribution to consolidating the foundations of this research field.

  15. A Method for solving scheduling problems by graph algorithms

    ZHOU Xiao, MIZUKI Takaaki, KUSAKARI Yishiyoki

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research on Priority Areas (B)

    Institution: Tohoku University

    1998 - 2000

    More details Close

    The scheduling problem was modeled by using the graph in this research. It is well-known that the coloring problem, from which the application to this problem is strongly expected, is NP-hard in general. So it is very unlikely that there exists an efficient algorithm to solve it. However, we showed that the problem can be solved efficiently for some restricted class of graphs. The results achieved for this research are chiefly four of the following. 1. We gave a linear algorithm to solve [g, f]-coloring problem for partial k-trees by a dynamic programming method. This result was published in Algorithmica(1999). 2. We give a linear algorithm to solve the total coloring problem for partial k-trees which is published in ISAAC' 99. Afterwards, we improved it for degenerate graphs which is published in ICALP' 01. 3. We gave a polynomial-time algorithm to solve the 1-vertex-coloring problem for partial k-trees which is published in IEICE Trans. on fundamentals of Electronics, Communication and Computer Science (2000). 4. We give a polynomial-time algorithm to solve the cost edge-coloring problem for trees which is published in COCOON' 01.

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

    周 暁

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 奨励研究(A)

    Institution: 東北大学

    1997 - 1998

    More details Close

    平成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. Paradigm for Designing Efficient Algorithms on Structured Graphs

    NISHIZEKI Takao, ZHOU Xiao, NAKANO Shin-ichi

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    1997 - 1998

    More details Close

    This project aimed to establish "Paradigm for Designing Efficient Algorithms on Structured Graphs. "We approached the project by taking up the unresolved problems of trees, series-parallel graphs, partialk-trees in structured graphs, and succeeded in finding the efficient algorithms for colorings, disjoint paths, graph drawings, as follows : - gave an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time OMICRON(n^2 logDELTA), where n is the number of vertices in T ; - gave an algorithm for finding a non crossing Steiner forest which runs in OMICRON(eta log eta) time in the case that all terminals are on the outer face of a biconnected plane graph G ; - presented an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time OMICRON(n^2 logDELTA), where eta is the number of vertices in T and DELTA is the maximum vertex-degree of T.This algorithm is fater than the best known for the case c = 1 ; - proved that the edge-disjoint paths problem is NP-complete for partial kappa-trees with some bounded kappa, say kappa = 3, although the problem is trivially solvable for trees ; - gave a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time OMICRON(eta^<7/>ROO<log eta>) for any plane graph of eta vertices. Since 1987 we have devoted ourselves to develop "Paradigm for Designing Efficient Algorithms on Structured Graphs" and succeeded in giving the best possible algorithms for some difficult problems. We are confident that we made a great contribution to consolidating the foundations of this research field.

Show all Show first 5