所属組織 |
大学院環境情報研究院 社会環境と情報部門 |
職名 |
准教授 |
研究キーワード |
グラフ理論、離散数学 |
ホームページ |
|
YNU研究拠点 |
|
関連SDGs |
小関 健太 (オゼキ ケンタ)
OZEKI Kenta
|
学内所属歴 【 表示 / 非表示 】
-
2019年4月-現在
専任 横浜国立大学 大学院環境情報研究院 社会環境と情報部門 准教授
-
2017年2月-2019年3月
専任 横浜国立大学 大学院環境情報研究院 社会環境と情報部門 特任教員(准教授)
-
2021年4月-現在
併任 横浜国立大学 大学院先進実践学環 准教授
-
2019年4月-現在
併任 横浜国立大学 大学院環境情報学府 情報メディア環境学専攻 准教授
-
2019年4月-現在
併任 横浜国立大学 大学院環境情報学府 情報環境専攻 准教授
著書 【 表示 / 非表示 】
-
IT Text 離散数学
松原良太,大嶌彰昇,藤田慎也,小関健太,中上川友樹,佐久間雅,津垣正男( 担当: 共著 , 範囲: 4章 グラフと木)
オーム社 2010年10月
記述言語:日本語 著書種別:教科書・概説・概論
情報系を学ぶ学生にとっての基礎数学として、わかりやすい言葉と高校までに学んだ範囲で離散数学を基礎からていねいに解説した教科書。システム開発者や他分野の方にも基礎概念の整理に役立つ一冊。
学位論文 【 表示 / 非表示 】
-
Hamilton Cycles, Paths and Spanning Trees in a Graph
Kenta Ozeki
2009年3月
学位論文(博士) 単著
論文 【 表示 / 非表示 】
-
A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs
MATSUI Yasuko, OZEKI Kenta
IEICE Transactions on Information and Systems 104 ( 3 ) 389 - 391 2021年
記述言語:英語 掲載種別:研究論文(学術雑誌) 出版者・発行元:一般社団法人 電子情報通信学会 共著
<p>This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with <i>n</i> vertices in O(<i>n</i>) time, and another one generates each <i>k</i>-edge-connected spanning subgraph of a general graph with <i>m</i> edges in O(<i>mT</i>) time, where <i>T</i> is the running time to check the <i>k</i>-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in <i>O</i>(<i>n</i><sup>2</sup>) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.</p>
-
Hamiltonicity of Graphs on Surfaces in Terms of Toughness and Scattering Number – A Survey
Ozeki, K.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13034 LNCS 74 - 95 2021年 [査読有り]
記述言語:英語 掲載種別:研究論文(学術雑誌) 共著
-
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
Ito, T. and Iwamasa, Y. and Kakimura, N. and Kamiyama, N. and Kobayashi, Y. and Maezawa, S.-I. and … 全著者表示
Ito, T. and Iwamasa, Y. and Kakimura, N. and Kamiyama, N. and Kobayashi, Y. and Maezawa, S.-I. and Nozaki, Y. and Okamoto, Y. and Ozeki, K. 閉じる
arXiv 2021年
記述言語:その他外国語 掲載種別:研究論文(学術雑誌) 共著
-
Thomassen's conjecture for line graphs of 3-hypergraphs
Li Binlong, Ozeki Kenta, Ryjacek Zdenek, Vrana Petr
DISCRETE MATHEMATICS 343 ( 6 ) 2020年6月 [査読有り]
記述言語:英語 掲載種別:研究論文(学術雑誌) 共著
-
Long Paths in Bipartite Graphs and Path-Bistar Bipartite Ramsey Numbers
Furuya Michitaka, Maezawa Shun-ichi, Ozeki Kenta
GRAPHS AND COMBINATORICS 36 ( 1 ) 167 - 176 2020年1月 [査読有り]
記述言語:英語 掲載種別:研究論文(学術雑誌) 共著
総説・解説記事等 【 表示 / 非表示 】
-
A forbidden pair for connected graphs to have spanning k-trees
Maezawa, S.-I. and Ozeki, K.
Journal of Graph Theory 99 ( 3 ) 509 - 519 2022年
記述言語:その他外国語 掲載種別:記事・総説・解説・論説等(大学・研究所紀要) 共著
-
The Alon-Tarsi number of K<sub>5</sub>-minor-free graphs
Abe, T. and Kim, S.-J. and Ozeki, K.
Discrete Mathematics 345 ( 4 ) 2022年
記述言語:その他外国語 掲載種別:記事・総説・解説・論説等(大学・研究所紀要) 共著
-
Covering projective planar graphs with three forests
Mukae, R. and Ozeki, K. and Sano, T. and Tazume, R.
Discrete Mathematics 345 ( 4 ) 2022年
記述言語:その他外国語 掲載種別:記事・総説・解説・論説等(大学・研究所紀要) 共著
-
エレガントな解答を求む 2021年4月号出題 2
小関 健太
数学セミナー 2021年4月 [依頼有り]
記述言語:日本語 掲載種別:記事・総説・解説・論説等(商業誌、新聞、ウェブメディア) 出版者・発行元:日本評論社 単著
図1 はあるホテルの見取り図で,斜線部が部屋で白
い部分が廊下を表している.すべての廊下には電灯が
ついており,丸数字が表すスイッチにより隣接する廊
下の電灯のon–off を切り替えられる.ただし1 つの
スイッチは連動しており,例えば1 のスイッチを押す
と,図2 のように,1 と2 の間の廊下,1 と3 の間の
廊下,1 と4 の間の廊下の3 つの電灯のon–off が同時
に変わってしまう.(他の廊下の電灯のon–off は変わ
らない)
(1) 以下のどの状況のときに全部の廊下の電灯をoff に
できるでしょうか?
(A) 全部の電灯がon.
(B) 1 と2 の間の廊下と5 と6 の間の廊下だけ
電灯がoff,他はon,
(C) 1 と2 の間の廊下と4 と5 の間の廊下だけ
電灯がoff,他はon,
(2) 他の状態からはじめたときや別のホテルでも考え
てみてください.すべてをoff にできるための必
要十分条件を,すっきりした形で言えないでしょ
うか?
(1) のみの解答でも構いませんので,ぜひ考えてみて
ください. -
The color number of cubic graphs having a spanning tree with a bounded number of leaves
Malnegro, A.A. and Malacas, G.A. and Ozeki, K.
Theory and Applications of Graphs 8 ( 2 ) 2021年
記述言語:その他外国語 掲載種別:記事・総説・解説・論説等(大学・研究所紀要) 共著
受賞 【 表示 / 非表示 】
-
2014年度 応用数学研究奨励賞
2015年03月 日本数学会 応用数学分科会 (g, f)-factors in directed graphs
受賞者:小関健太 -
日本数学会賞建部賢弘賞奨励賞
2013年03月 日本数学会
受賞者:小関健太
科研費(文科省・学振)獲得実績 【 表示 / 非表示 】
-
グラフの strong Gallai-Ramsey 理論の提案と発展
研究課題/領域番号:22F20324 2022年4月 - 2024年3月
特別研究員奨励費
担当区分:その他 資金種別:競争的資金
-
数学アプローチによる組合せ遷移の展開:活用事例を手がかりとして新解法へ
研究課題/領域番号:20H05795 2020年10月 - 2023年3月
学術変革領域研究(B)
担当区分:研究分担者
-
被覆グラフを利用した巨大グラフ解析へのアプローチ
研究課題/領域番号:19H01803 2019年4月 - 2022年3月
基盤研究(B)
-
トポロジー的な性質を持つハミルトン閉路を利用した, 閉曲面上のグラフの頂点彩色 研究課題
2018年4月 - 2021年3月
科学研究費補助金 基盤研究(C)
代表者:小関 健太
資金種別:競争的資金
本研究の目的は,閉曲面上のグラフについて,ハミルトン閉路を利用した新しい彩色の手法を提案することである
その他競争的資金獲得・外部資金受入状況 【 表示 / 非表示 】
-
グラフのハミルトン閉路に関する Nash-Williams と Grunbaum 予想の解決
2014年11月 - 2015年11月
公益財団法人 住 友 財 団 住友財団 基礎科学研究助成
代表者:小関 健太
グラフとは,頂点集合と辺集合(頂点集合の二元部分集合族)からなる構造として定義される.グラフの全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路と呼び,ちょうど一度ずつ通る道をハミルトン道と呼ぶ.「与えられたグラフがハミルトン閉路をもつかどうか決定する」という問題は,組み合わせ最適化の分野において特に重要な巡回セールスマン問題とも密接に関係しているため,グラフ理論の中でも非常に多くの研究がなされている.
ここで, グラフを平面グラフなどトポロジー的な閉曲面上のものに限ると,この問題は四色定理とも関わりを持つこともあり,多くの研究が行われている.本研究もこの流れに沿うものである.閉曲面上のグラフのハミルトン性については,表 1 にあるように 1956年の Tutte の結果以来様々な研究者が研究を行ってきた.例えば,1983年に Thomassen が「平面上の任意の 4-連結グラフはハミルトン連結である」と示したことを意味している.なお,グラフが,``任意の 2頂点に対し,それらを結ぶハミルトン道が存在する'' という性質を満たすとき,ハミルトン連結であるという.
このように,この分野についていくつかの結果が示されているが,未解決な部分も存在する.特に,次の命題は,40年以上未解決であり,グラフ理論全体の中でも重要なものとなっている.この予想の完全解決が研究の目的である.
予想 (Grunbaum `70, Nash-Williams `73)
トーラス上の任意の 4-連結グラフはハミルトン閉路を持つ.
研究発表 【 表示 / 非表示 】
-
グラフの出次数制約のある向き付け
小関健太
第31回 位相幾何学的グラフ理論研究集会
開催年月日: 2019年11月
記述言語:英語 会議種別:口頭発表(一般)
-
An orientation of graphs with out-degree constraint
Kenta Ozeki [招待有り]
The 2nd East Asia Workshop on Extremal and Structural Graph Theory
開催年月日: 2019年11月
記述言語:英語 会議種別:口頭発表(招待・特別)
-
Spanning trees with few leaves in graphs on surfaces
Kenta Ozeki [招待有り]
International Conference on Graph Theory, Combinatorics and Applications
開催年月日: 2019年6月
記述言語:英語 会議種別:口頭発表(一般)
-
Spanning trees with few number of leaves in 4-connected graphs on higher genus surface
Kenta Ozeki
Structural Graph Theory and Graph Colorings
開催年月日: 2019年4月
記述言語:英語 会議種別:口頭発表(一般)
-
Spanning trees with few leaves in graphs on surfaces
Kenta Ozeki
Joint Mathematics Meetings American Mathematical Society, Mathematical Association of America
開催年月日: 2019年1月
記述言語:英語 会議種別:口頭発表(一般)
開催地:Baltimore
学会誌・論文誌編集等 【 表示 / 非表示 】
-
Journal of Algebra Combinatorics Discrete Structures and Applications
Editorial Board
2014年5月-現在 -
Theory and Applications of Graphs
Editorial Board
2014年1月-現在 -
Graphs and Combinatorics
Managing Editor
1985年1月-現在
担当授業科目(学内) 【 表示 / 非表示 】
-
2022年度 離散数学Ⅱ
理工学部
-
2022年度 離散数学Ⅰ
理工学部
-
2022年度 数理情報特論演習Ⅳ
大学院環境情報学府
-
2022年度 数理情報特論演習Ⅲ
大学院環境情報学府
-
2022年度 数理情報特論演習Ⅱ
大学院環境情報学府