小関 健太 (オゼキ ケンタ)

OZEKI Kenta

所属組織

大学院環境情報研究院 社会環境と情報部門

職名

准教授

研究キーワード

グラフ理論、離散数学

ホームページ

http://tgt.ynu.ac.jp/ozeki/

YNU研究拠点

位相幾何学的グラフ理論研究拠点

関連SDGs




ORCID  https://orcid.org/0000-0003-3118-0086

学歴 【 表示 / 非表示

  •  
    -
    2009年3月

    慶應義塾大学   理工学研究科   基礎理工学専攻   博士課程   修了

学位 【 表示 / 非表示

  • 博士(理学) - 慶應義塾大学

  • 修士(理学) - 慶應義塾大学

学内所属歴 【 表示 / 非表示

  • 2019年4月
    -
    現在

    専任   横浜国立大学   大学院環境情報研究院   社会環境と情報部門   准教授  

  • 2017年2月
    -
    2019年3月

    専任   横浜国立大学   大学院環境情報研究院   社会環境と情報部門   特任教員(准教授)  

  • 2021年4月
    -
    現在

    併任   横浜国立大学   大学院先進実践学環   准教授  

  • 2019年4月
    -
    現在

    併任   横浜国立大学   大学院環境情報学府   情報メディア環境学専攻   准教授  

  • 2019年4月
    -
    現在

    併任   横浜国立大学   大学院環境情報学府   情報環境専攻   准教授  

全件表示 >>

学外略歴 【 表示 / 非表示

  • 2012年11月
    -
    2017年1月

      国立情報学研究所   特任助教

所属学協会 【 表示 / 非表示

  • 2008年4月
    -
    現在
     

    日本数学会

研究分野 【 表示 / 非表示

  • 自然科学一般 / 応用数学、統計数学

 

著書 【 表示 / 非表示

  • 曲面上のグラフ理論

    中本 敦浩, 小関 健太( 担当: 単著)

    サイエンス社  2021年  ( ISBN:9784781915302

    CiNii

     詳細を見る

    記述言語:日本語 著書種別:学術書

  • 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年

    DOI

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人 電子情報通信学会   共著  

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

    その他リンク: https://ci.nii.ac.jp/naid/130007993194

  • 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年  [査読有り]

    DOI Scopus

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   共著  

  • 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 … 全著者表示

    arXiv   2021年

    Scopus

     詳細を見る

    記述言語:その他外国語   掲載種別:研究論文(学術雑誌)   共著  

  • Thomassen's conjecture for line graphs of 3-hypergraphs

    Li Binlong, Ozeki Kenta, Ryjacek Zdenek, Vrana Petr

    DISCRETE MATHEMATICS   343 ( 6 )   2020年6月  [査読有り]

    DOI Web of Science Scopus

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   共著  

  • 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月  [査読有り]

    DOI Web of Science Scopus

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   共著  

全件表示 >>

総説・解説記事等 【 表示 / 非表示

  • 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年

    DOI Scopus

     詳細を見る

    記述言語:その他外国語   掲載種別:記事・総説・解説・論説等(大学・研究所紀要)   共著  

  • 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年

    DOI Scopus

     詳細を見る

    記述言語:その他外国語   掲載種別:記事・総説・解説・論説等(大学・研究所紀要)   共著  

  • Covering projective planar graphs with three forests

    Mukae, R. and Ozeki, K. and Sano, T. and Tazume, R.

    Discrete Mathematics   345 ( 4 )   2022年

    DOI Scopus

     詳細を見る

    記述言語:その他外国語   掲載種別:記事・総説・解説・論説等(大学・研究所紀要)   共著  

  • エレガントな解答を求む 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年

    DOI Scopus

     詳細を見る

    記述言語:その他外国語   掲載種別:記事・総説・解説・論説等(大学・研究所紀要)   共著  

全件表示 >>

受賞 【 表示 / 非表示

  • 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年度   数理情報特論演習Ⅱ

    大学院環境情報学府

全件表示 >>

担当経験のある授業科目(学外) 【 表示 / 非表示

  • 有限数学 第2

    機関名:慶應義塾大学理工学部