Tokushima University / Educator and Researcher Directory --- Nakayama, Shin-ichi

Field of Study

○	Information Science

Subject of Study

○	Development of Optimization Algorithms (algorithm, computational complexity, graph theory)

Book / Paper

Book:

1.	Motohiro Ishida, Shinki Oyabu, Tetsushi Ueta, Hidekazu Kakei, Kazuhide Kanenishi, Hiroki Tanioka, Shin-ichi Nakayama and Akihiro Haga : 情報科学入門統計・データサイエンス・AI, 技術評論社, Mar. 2021.
2.	Shin-ichi Nakayama, Hidekazu Kakei, Toshiaki Itoh and Mamoru Ohashi : 情報科学入門, GAKUJUTU TOSHO SHUPPAN-SHA, Tokyo, Apr. 2007.
3.	Mamoru Ohashi, Toshiaki Itoh, Shin-ichi Nakayama, Taro Mori and Hidekazu Kakei : マスターしよう情報リテラシー, GAKUJUTU TOSHO SHUPPAN-SHA, Tokyo, Apr. 2003. (Summary) 大学における初心者向き授業用教科書.
4.	Mamoru Ohashi, Toshiaki Itoh and Shin-ichi Nakayama : 改訂版これならできる情報リテラシー, GAKUJUTU TOSHO SHUPPAN-SHA, Tokyo, Mar. 2001. (Summary) 大学におけるパソコン初心者向き授業用教科書(改訂版)，GNUライセンス化し広く教育関係機関へ無料配布，WEB化しOPEN化．教科書のネット上での共同開発等を提案し活動．
5.	Mamoru Ohashi, Toshiaki Itoh and Shin-ichi Nakayama : これならできる情報リテラシー, GAKUJUTU TOSHO SHUPPAN-SHA, Tokyo, Apr. 1999. (Summary) 大学におけるパソコン初心者向き授業用教科書，GNUライセンス化し広く教育関係機関へ無料配布，WEB化しOPEN化．教科書のネット上での共同開発等を提案·活動．

Academic Paper (Judged Full Paper):

1.	Shin-ichi Nakayama and Shigeru Masuyama : A polynomial-time algorithm for finding a spanning tree with non-terminal set `V_NT` on circular-arc graphs, IEICE Transactions on Information and Systems, Vol.E105-D, No.8, 2022. (Link to Publication Site) ● Publication site (DOI): 10.1587/transinf.2021EDP7175 (Link to Search Site for Scientific Articles) ● Search Scopus @ Elsevier (DOI): 10.1587/transinf.2021EDP7175 (DOI: 10.1587/transinf.2021EDP7175)
2.	Shin-ichi Nakayama and Shigeru MASUYAMA : A Linear Time Algorithm for Finding a Minimum Spanning Tree with Non-Terminal Set `V_NT` on Series-Parallel Graphs, IEICE Transactions on Information and Systems, Vol.E102-D, No.4, 826-835, 2019. (Link to Publication Site) ● Publication site (DOI): 10.1587/transinf.2018EDP7232 (Link to Search Site for Scientific Articles) ● Summary page in Scopus @ Elsevier: 2-s2.0-85064004010 (DOI: 10.1587/transinf.2018EDP7232, Elsevier: Scopus)
3.	Shin-ichi Nakayama and Shigeru Masuyama : A linear-time algorithm for finding a spanning tree with non-terminal set `V_NT` on interval graphs, IEICE Transactions on Information and Systems, Vol.E101-D, No.9, 2235-2246, 2018. (Summary) <p>Given a graph <i>G</i>=(<i>V</i>,<i>E</i>) where <i>V</i> and <i>E</i> are a vertex and an edge set, respectively, specified with a subset <i>V<sub>NT</sub></i> of vertices called a <i>non</i>-<i>terminal</i> <i>set</i>, the spanning tree with non-terminal set <i>V<sub>NT</sub></i> is a connected and acyclic spanning subgraph of <i>G</i> that contains all the vertices of <i>V</i> where each vertex in a non-terminal set is not a leaf. The complexity of finding a spanning tree with non-terminal set <i>V<sub>NT</sub></i> on general graphs where each edge has the weight of one is known to be NP-hard. In this paper, we show that if <i>G</i> is an interval graph then finding a spanning tree with a non-terminal set <i>V<sub>NT</sub></i> of <i>G</i> is linearly-solvable when each edge has the weight of one.</p> (Keyword) spanning tree / interval graph / algorithm (Link to Publication Site) ● Publication site (DOI): 10.1587/transinf.2018EDP7047 (Link to Search Site for Scientific Articles) ● CiNii @ National Institute of Informatics (CRID): 1390564238016798720 ● Summary page in Scopus @ Elsevier: 2-s2.0-85053847123 (DOI: 10.1587/transinf.2018EDP7047, CiNii: 1390564238016798720, Elsevier: Scopus)
4.	Shin-ichi Nakayama and Shigeru MASUYAMA : A linear time algorithm for finding a minimum spanning tree with non-terminal set V_NT on outerplanar graphs., IEICE Transactions on Information and Systems, Vol.E100-D, No.3, 434-443, 2017. (Link to Publication Site) ● Publication site (DOI): 10.1587/transinf.2016FCP0010 (Link to Search Site for Scientific Articles) ● Summary page in Scopus @ Elsevier: 2-s2.0-85016094595 (DOI: 10.1587/transinf.2016FCP0010, Elsevier: Scopus)
5.	Shin-ichi Nakayama and Shigeru MASUYAMA : A linear time algorithm for finding a spanning tree with non-terminal set $V_{NT}$ on cographs., IEICE Transactions on Information and Systems, Vol.E99-D, No.10, 2574-2584, 2016. (Link to Publication Site) ● Publication site (DOI): 10.1587/transinf.2016EDP7021 (Link to Search Site for Scientific Articles) ● Search Scopus @ Elsevier (DOI): 10.1587/transinf.2016EDP7021 (DOI: 10.1587/transinf.2016EDP7021)
6.	Shin-ichi Nakayama and Shigeru MASUYAMA : A Polynomial Time Algorithm for Solving a 2-Tuple Domination Problem on Permutation Graphs, 回路とシステムシンポジウム, Vol.vol.26, 231-236, 2013. (Link to Search Site for Scientific Articles) ● CiNii @ National Institute of Informatics (CRID): 1520853833975399296 (CiNii: 1520853833975399296)
7.	Shin-ichi Nakayama and Shigeru Masuyama : A Polynomial Time Algorithm for Obtaining Minimum Edge Ranking on Two-connected Outerplanar Graphs, Information Processing Letters, No.103, 216-221, 2007. (Link to Publication Site) ● Publication site (DOI): 10.1016/j.ipl.2007.03.014 (Link to Search Site for Scientific Articles) ● Summary page in Scopus @ Elsevier: 2-s2.0-34250792740 (DOI: 10.1016/j.ipl.2007.03.014, Elsevier: Scopus)
8.	Shin-ichi Nakayama and Shigeru Masuyama : A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs, IEICE Transactions on Information and Systems, Vol.89, No.8, 2357-2363, 2006. (Summary) The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs. (Keyword) algorithm / vertex ranking / spanning tree / outerplanar graph (Link to Publication Site) ● Publication site (DOI): 10.1093/ietisy/e89-d.8.2357 (Link to Search Site for Scientific Articles) ● CiNii @ National Institute of Informatics (CRID): 1570009752661185152 ● Search Scopus @ Elsevier (DOI): 10.1093/ietisy/e89-d.8.2357 (DOI: 10.1093/ietisy/e89-d.8.2357, CiNii: 1570009752661185152)
9.	Keizo Miyata, Shigeru Masuyama, Shin-ichi Nakayama and Liang Zhao : NP-hardness proof and an approximation algorithm for the maximum vertex ranking spanning tree problem, Discrete Applied Mathematics, Vol.154, No.16, 2402-2410, 2006. (Link to Publication Site) ● Publication site (DOI): 10.1016/j.dam.2006.04.016 (Link to Search Site for Scientific Articles) ● Search Scopus @ Elsevier (DOI): 10.1016/j.dam.2006.04.016 (DOI: 10.1016/j.dam.2006.04.016)
10.	Shin-ichi Nakayama and Shigeru Masuyama : An algorithm for solving the minimum vertex ranking spanning tree problem on interval graphs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.86, No.5, 1019-1026, 2003. (Summary) The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n^3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph. (Keyword) algorithm / vertex ranking / spanning tree / interval graph (Link to Search Site for Scientific Articles) ● CiNii @ National Institute of Informatics (CRID): 1570291227388262016 ● Summary page in Scopus @ Elsevier: 2-s2.0-0141903395 (CiNii: 1570291227388262016, Elsevier: Scopus)
11.	Shin-ichi Nakayama and Shigeru Masuyama : An Algorithm for Finding Two Edge-Disjoint Paths in Tournaments, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E83-A, No.12, 2672-2678, 2000. (Summary) This paper presents an O(n^2)-time algorithm for constructing two edge-disjoint paths connecting two given pairs of vertices in a given tournament graph. It improves the time complexity of a previously known O(n^4)-time algorithm. (Keyword) edge-disjoint path / tournament graph / algorithm (Link to Search Site for Scientific Articles) ● CiNii @ National Institute of Informatics (CRID): 1570291227426560512 ● Summary page in Scopus @ Elsevier: 2-s2.0-0034498797 (CiNii: 1570291227426560512, Elsevier: Scopus)
12.	Shigeru Masuyama and Shin-ichi Nakayama : What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples, IEICE Transactions on Information and Systems, Vol.E83-D, No.3, 541-549, 2000. (Summary) This paper analyzes what structural features of graph problems allow efficient parallel algorithms. We survey some parallel algorithms for typical problems on three kinds of graphs, outerplanar graphs, trapeziod graphs and in-tournament graphs. Our results on the shortest path problem, the longest path problem and the maximum flow problem on outerplanar graphs, the minimum-weight connected dominating set problem and the coloring problem on trapezoid graphs and Hamiltonian path and Hamiltonian cycle problem on in-tournament graphs are adopted as working examples. (Keyword) parallel graph algorithms / structure and complexity / outerplanar graph / trapezoid graph / in-tournament graph (Link to Search Site for Scientific Articles) ● CiNii @ National Institute of Informatics (CRID): 1570291227534662784 (CiNii: 1570291227534662784)
13.	Shin-ichi Nakayama and Shigeru Masuyama : Parallel Algorithms for Finding a Hamiltonian Path and a Hamiltonian Cycle in an In-Tournament Graph, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E81-A, No.5, 757-767, 1998.
14.	Shin-ichi Nakayama and Shigeru Masuyama : A Parallel Algorithm for Solving the Coloring Problem on Trapezoid Graphs, Information Processing Letters, Vol.62, 323-327, 1997.
15.	Shin-ichi Nakayama and Shigeru Masuyama : A Parallel Algorithm for Finding a Minimum-Weight Connected Dominating Set on Trapezoid Graphs, Mathematica Japonica, Vol.45, No.1, 165-171, 1997.
16.	Shin-ichi Nakayama and Shigeru Masuyama : 2連結グラフ上の与えられた節点を中心とする全域木を求める並列アルゴリズム, The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, Vol.J79DI, No.5, 299-302, 1996.
17.	Shin-ichi Nakayama and Shigeru Masuyama : 外平面グラフ上の最大流を求める並列アルゴリズム, The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, Vol.J79DI, No.5, 226-236, 1996.
18.	Shin-ichi Nakayama and Shigeru Masuyama : 外平面グラフ上のst-最短経路を求める並列アルゴリズム, The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, Vol.J78DI, No.11, 867-877, 1995.
19.	Shin-ichi Nakayama and Shigeru Masuyama : 外平面グラフの最長路問題を解く並列アルゴリズム, The Transactions of the Institute of Electronics, Information and Communication Engineers D-I, Vol.J78DI, No.6, 563-568, 1995.

Academic Paper (Unrefereed Paper):

1.	Shin-ichi Nakayama and Shigeru Masuyama : A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs, Natural Science Research, Faculty of Integrated Arts and Sciences, The University of Tokushima, 71-80, 1997. (Tokushima University Institutional Repository) ● Metadata: 118 (Tokushima University Institutional Repository: 118)

Proceeding of International Conference:

1.	Shin-ichi Nakayama and Shigeru Masuyama : A Polynomial Time Algorithm for Obtaining the Minimum Vertex Ranking Spanning Tree on Outerplanar Graphs, INFORMS International Hong Kong 2006, Hong Kong, China, Jun. 2006.
2.	Shin-ichi Nakayama and Shigeru MASUYAMA : An O(n^3) Time Algorithm for obtaining the Minimum Vertex Ranking Spanning Tree on Permutation Graphs, HJ2005, 250-256, Hungry, 2005.
3.	Shin-ichi Nakayama and Shigeru Masuyama : An O(n3) Time Algorithm for Obtaining the Minimum Vertex Ranking Spanning Tree on Interval Graphs, HJ2003, Tokyo, Jan. 2003.

Proceeding of Domestic Conference:

1.	Kei Chikahisa and Shin-ichi Nakayama : 通過指定箇所がある格子上における最短経路問題を解くプログラム開発について, 2022 年日本オペレーションズ・リサーチ学会中国・四国地区 SSOR, Nov. 2022.
2.	Kohei Ihii and Shin-ichi Nakayama : 多角形面積最小化問題を解くプログラム開発, 日本オペレーションズ・リサーチ学会中国・四国地区 SSOR, 31-32, Nov. 2021.
3.	Shin-ichi Nakayama : 非端末節点集合を伴う最小全域木問題を解くアルゴリズムについて, OR学会SSOR中部支部, Aug. 2021.
4.	近藤亨一, 坂本彩奈 and Shin-ichi Nakayama : ある種のクラス編成問題を解くプログラム開発, 日本オペレーションズ・リサーチ学会中国・四国地区 SSOR, 24-25, Nov. 2020.
5.	Koichi Kondoh and Shin-ichi Nakayama : クラス編成問題を解くプログラム開発, 日本オペレーションズ・リサーチ学会中国・四国地区 SSOR, Nov. 2019.
6.	Jun Tsukamoto and Shin-ichi Nakayama : 非端末節点集合を伴う最小全域木問題を解く各種メタヒューリスティクスについて, 日本オペレーションズ・リサーチ学会中国・四国地区 SSOR, Nov. 2019.
7.	Shin-ichi Nakayama : 最小全域木に関する問題の解法について, 日本オペレーションズ・リサーチ学会中国・四国支部講演会, Mar. 2019.
8.	塚本淳 and Shin-ichi Nakayama : 非端末節点集合を伴う最小全域木問題を解くプログラム開発, 日本OR学会中四国支部SSOR, 15-16, Sep. 2018.
9.	塚本淳 and Shin-ichi Nakayama : 非端末節点集合を伴う全域木問題を解くアルゴリズム開発, 中国・四国地区SSOR, 18-19, Sep. 2017.
10.	Shin-ichi Nakayama and 増山繁 : 区間グラフ上における非端末節点集合を伴う全域木を求める線形時間アルゴリズム, 日本OR学会春季研究発表会, Mar. 2016.
11.	Shin-ichi Nakayama and Shigeru MASUYAMA : A linear time algorithm for finding a spanning tree with non-terminal set $V_{NT}$ on cographs, IEICE Technical Report, Vol.114, No.199, 9-16, Sep. 2014.
12.	Shin-ichi Nakayama and 増山繁 : 置換グラフ上における最少2-組支配集合を求める多項式アルゴリズム, Sep. 2012.
13.	増山繁 and Shin-ichi Nakayama : -, 「新世代計算限界と地球環境問題」講演論文集, 89-95, 2006.
14.	Shin-ichi Nakayama and 増山繁 : 置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム, 冬のLAシンポジウム, 2004.
15.	宮田敬三, 増山繁 and Shin-ichi Nakayama : 最小節点ランキング全域木問題の計算複雑度, 回路とシステム軽井沢ワークショップ論文集, 645-650, 2004.
16.	Shin-ichi Nakayama and 増山繁 : 置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム, 情報処理学会研究報告「アルゴリズム」, Vol.AL92, No.6, 2003.
17.	宮田敬三, 増山繁 and Shin-ichi Nakayama : 最小節点ランキング全域木問題の計算複雑性について, 電子情報通信学会コンピュテーション研究会, 2003.
18.	Shin-ichi Nakayama and 増山繁 : ある種のデータ収集問題の部分クラスに対する効率的解法, スケジューリング·シンポジウム2002, Oct. 2002.
19.	Shin-ichi Nakayama and 増山繁 : グラフの構造的特徴と効率の良い並列アルゴリズムについて, 「アルゴリズム工学」研究集会, Oct. 2000.
20.	Shin-ichi Nakayama and 増山繁 : 並列グラフアルゴリズムにおける構造と計算量, 3学会(OR学会中部支部，QC学会中部支部，JIMA中部支部)合同研究発表会, Jul. 1999.
21.	Shin-ichi Nakayama and 増山繁 : An Algorithm for Finding Two Edge-Disjoint Paths in Tournaments, SSOR, Aug. 1998.
22.	Shin-ichi Nakayama and 増山繁 : グラフの構造的特徴と効率の良い並列アルゴリズムについて, 「アルゴリズム工学」研究集会, Jul. 1997.
23.	Shin-ichi Nakayama and 増山繁 : 台形グラフの点彩色問題を解く並列アルゴリズム, 日本OR学会春季研究発表会, Apr. 1997.
24.	Shin-ichi Nakayama and 増山繁 : in-トーナメントグラフ上のハミルトン閉路を求める並列アルゴリズム, 日本OR学会秋季研究発表会, Sep. 1979.

Et cetera, Workshop:

1.	Shin-ichi Nakayama : 台形グラフ，および，そのサブグラフ上におけるc-ランキング問題を解く多項式時間アルゴリズムについて, 日本OR学会中国・四国支部定例シンポジウム, Nov. 2010.

Grants-in-Aid for Scientific Research (KAKEN Grants Database @ NII.ac.jp)

Webコンテンツ活用に関連した離散最適化問題の研究 (Project/Area Number: 16092213 )
ネットワーク上におけるデータ統合問題に関する数理的解法 (Project/Area Number: 15700018 )
グラフの構造的特徴と効率の良い並列アルゴリズムに関する研究 (Project/Area Number: 13780242 )
経路問題に関するアルゴリズムの研究 (Project/Area Number: 09780290 )
Search by Researcher Number (50284279)

Associate Professor : Nakayama, Shin-ichi

Research

Field of Study

Subject of Study

Book / Paper

Book:

Academic Paper (Judged Full Paper):

Academic Paper (Unrefereed Paper):

Proceeding of International Conference:

Proceeding of Domestic Conference:

Et cetera, Workshop:

Grants-in-Aid for Scientific Research (KAKEN Grants Database @ NII.ac.jp)