主な成果| 組合せ遷移＠学術変革領域研究(B)

Submodular reassignment problem for reallocating agents to tasks with synergy effects

Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Discrete Optimization, Vol. 44, pp. 100631, 2022

DOI: 10.1016/j.disopt.2021.100631
The Alon-Tarsi number of K5-minor-free graphs

Toshiki Abe, Seog-Jin Kim, Kenta Ozeki

Discrete Mathematics, Vol. 345, pp. 112764, 2022

DOI: 10.1016/j.disc.2021.112764
Covering projective planar graphs with three forests

Raiji Mukae, Kenta Ozeki, Terukazu Sano, Ryuji Tazume

Discrete Mathematics, Vol. 345, pp. 112748, 2022

DOI: 10.1016/j.disc.2021.112748
Parameterized complexity of (A, l)-path packing

Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi

Algorithmica, Vol. 84, pp. 871-895, 2022

DOI: 10.1007/s00453-021-00875-y
Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model

Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida

SIAM Journal on Discrete Mathematics, Vol. 36, pp. 355-382, 2022

DOI: 10.1137/20M1357317
A forbidden pair for connected graphs to have spanning k-trees

Shun-ichi Maezawa, Kenta Ozeki

Journal of Graph Theory, Vol. 99, pp. 509-519, 2022

DOI: 10.1002/jgt.22752
Independent set reconfiguration on directed graphs

Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa

arXiv 2203.13435, 2022

DOI: 10.48550/arXiv.2203.13435
Reconfiguration of regular induced subgraphs

Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa

Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 35-46, 2022

DOI: 10.1007/978-3-030-96731-4_4
Path cover problems with length cost

Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita

Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 396-408, 2022

DOI: 10.1007/978-3-030-96731-4_32
Happy set problem on subclasses of co-comparability graphs

Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 149-160, 2022

DOI: 10.1007/978-3-030-96731-4_13
Reconfiguration of spanning trees with degree constraint or diameter constraint

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

Proc. of 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Leibniz International Proceedings in Informatics, Vol. 219, pp. 15:1-15:21, 2022

DOI: 10.4230/LIPIcs.STACS.2022.15
An O(n^2)-time algorithm for computing a max-min 3-dispersion on a point set in convex position

Yasuaki Kobayashi, Shin-Ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka

IEICE Transactions on Information and Systems, Vol. E105-D, pp. 503-507, 2022

DOI: 10.1587/transinf.2021FCP0013
Multi-pass streaming algorithms for monotone submodular function maximization

Chien-Chung Huang, Naonori Kakimura

Theory of Computing Systems, Vol. 66, pp. 354-394, 2022

DOI: 10.1007/s00224-021-10065-6
Finding shortest non-separating and non-disconnecting paths

Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi

arXiv 2202.09718, 2022

DOI: 10.48550/arXiv.2202.09718
Sorting balls and water: equivalence and computational complexity

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

arXiv 2202.09495, 2022

DOI: 10.48550/arXiv.2202.09495
A framework to design approximation algorithms for finding diverse solutions in combinatorial problems

Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi

arXiv 2201.08940, 2022

DOI: 10.48550/arXiv.2201.08940
An approximation algorithm for k-best enumeration of minimal connected edge dominating sets with cardinality constraints

Kazuhiro Kurita, Kunihiro Wasa

arXiv 2201.08647, 2022

DOI: 10.48550/arXiv.2201.08647
Reconfiguration of spanning trees with degree constraint or diameter constraint

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

arXiv 2201.04354, 2022

DOI: 10.48550/arXiv.2201.04354
On the security number of the Cartesian product of graphs

Marko Jakovac, Yota Otachi

Discrete Applied Mathematics, Vol. 304, pp. 119-128, 2021

DOI: 10.1016/j.dam.2021.07.030
Distributed reconfiguration of spanning trees

Yukiko Yamauchi, Naoyuki Kamiyama, Yota Otachi

Proc. of 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021), Lecture Notes in Computer Science, Vol. 13046, pp. 516-520, 2021

DOI: 10.1007/978-3-030-91081-5_40
Reconfiguration of regular induced subgraphs

Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa

arXiv 2111.13476, 2021

DOI: 10.48550/arXiv.2111.13476
Efficient enumeration of dominating sets for sparse graphs

Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno

Discrete Applied Mathematics, Vol. 303, pp. 283-295, 2021

DOI: 10.1016/j.dam.2021.06.004
Low-congestion shortcut and graph parameters

Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

Distributed Computing, Vol. 34, pp. 349-365, 2021

DOI: 10.1007/s00446-021-00401-x
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

arXiv 2110.11585, 2021

DOI: 10.48550/arXiv.2110.11585
Computational complexity of jumping block puzzles

Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara

Proc. of 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science, Vol. 13025, pp. 655-667, 2021

DOI: 10.1007/978-3-030-89543-3_54
Reconfiguring directed trees in a digraph

Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

Proc. of 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science, Vol. 13025, pp. 343-354, 2021

DOI: 10.1007/978-3-030-89543-3_29
Decremental optimization of vertex-coloring under the reconfiguration framework

Yusuke Yanagisawa, Yuma Tamura, Akira Suzuki, Xiao Zhou

Proc. of 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science, Vol. 13025, pp. 355-366, 2021

DOI: 10.1007/978-3-030-89543-3_30
Proper colorings of plane quadrangulations without rainbow faces

Kengo Enami, Kenta Ozeki, Tomoki Yamaguchi

Graphs and Combinatorics, Vol. 37, pp. 1873-1890, 2021

DOI: 10.1007/s00373-021-02350-5
Locating evacuation centers optimally in path and cycle networks

Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, Junichi Teruyama

Proc. of 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021), Open Access Series in Informatics, Vol. 96, pp. 13:1-13:19, 2021

DOI: 10.4230/OASIcs.ATMOS.2021.13
日本応用数理学会第18回若手優秀講演賞

岩政勇仁 (京都大学)
「2×2型分割多項式行列の行列式次数を求める組合せ的多項式時間アルゴリズム」

2022年6月17日受賞
Dynamic bipartite matching market with arrivals and departures

Naonori Kakimura, Donghao Zhu

Proc. of 17th Conference on Web and Internet Economics (WINE 2021), Lecture Notes in Computer Science, Vol. 13112, pp. 544, 2021

DOI: 10.1007/978-3-030-94676-0
Max-min 3-dispersion problems

Takashi Horiyama, Shin-Ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E104-A, pp. 1101-1107, 2021

DOI: 10.1587/transfun.2020DMP0003
On the complexity of fair house allocation

Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong

Operations Research Letters, Vol. 49, pp. 572-577, 2021

DOI: 10.1016/j.orl.2021.06.006
On 3-polytopes with non-Hamiltonian prisms

Daiki Ikegami, Shun-ichi Maezawa, Carol T. Zamfirescu

Journal of Graph Theory, Vol. 97, pp. 569-577, 2021

DOI: 10.1002/jgt.22672
Color number of cubic graphs having spanning tree with bounded number of leaves

Analen A. Malnegro, Gina A. Malacas, Kenta Ozeki

Theory and Applications of Graphs, Vol. 8, pp. Article 1, 2021

DOI: 10.20429/tag.2021.080201
2-Factors of cubic bipartite graphs

Nastaran Haghparast, Kenta Ozeki

Discrete Mathematics, Vol. 344, pp. 112357, 2021

DOI: 10.1016/j.disc.2021.112357
Longest common subsequence in sublinear space

Masashi Kiyomi, Takashi Horiyama, Yota Otachi

Information Processing Letters, Vol. 168, pp. 106084, 2021

DOI: 10.1016/j.ipl.2020.106084
ClusterSets: Optimizing planar clusters in categorical point data

Jakob Geiger, Sabine Cornelsen, Jan-Henrik Haunert, Philipp Kindermann, Tamara Mchedlidze, Martin Nöllenburg, Yoshio Okamoto, Alexander Wolff

Computer Graphics Forum, Vol. 40, pp. 471-481, 2021

DOI: 10.1111/cgf.14322
A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura

Theoretical Computer Science, Vol. 874, pp. 32-41, 2021

DOI: 10.1016/j.tcs.2021.05.008
Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Koji Watase

Theoretical Computer Science, Vol. 873, pp. 87-113, 2021

DOI: 10.1016/j.tcs.2021.05.003
A (probably) optimal algorithm for bisection on bounded-treewidth graphs

Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone

Theoretical Computer Science, Vol. 873, pp. 38-46, 2021

DOI: 10.1016/j.tcs.2021.04.023
Finding diverse trees, paths, and more

Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi

Proc. of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol. 35, pp. 3778-3786, 2021

DOI:
Polynomial-delay enumeration of large maximal matchings

Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa

arXiv 2105.04146, 2021

DOI: 10.48550/arXiv.2105.04146
Algorithms for gerrymandering over graphs

Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Theoretical Computer Science, Vol. 868, pp. 30-45, 2021

DOI: 10.1016/j.tcs.2021.03.037
A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with $2 \time 2$ submatrices

Yuni Iwamasa

Proc. of 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021), Lecture Notes in Computer Science, Vol. 12707, pp. 119-133, 2021

DOI: 10.1007/978-3-030-73879-2_9
Exploring the gap between treedepth and vertex cover through vertex integrity

Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi

Proc. of 12th International Conference on Algorithms and Complexity (CIAC 2021), Lecture Notes in Computer Science, Vol. 12701, pp. 271-285, 2021

DOI: 10.1007/978-3-030-75242-2_19
A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $2 \times 2$ submatrices

Yuni Iwamasa

arXiv 2104.14841, 2021

DOI: 10.48550/arXiv.2104.14841
Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Tsuyoshi Yagita

Theoretical Computer Science, Vol. 865, pp. 131-140, 2021

DOI: 10.1016/j.tcs.2021.03.006
Optimal reconfiguration of optimal ladder lotteries

Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa

Theoretical Computer Science, Vol. 859, pp. 57-69, 2021

DOI: 10.1016/j.tcs.2021.01.009
Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights

Tetsuya Fujie, Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Yuki Tokuni

Proc. of 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), Lecture Notes in Computer Science, Vol. 12635, pp. 52-64, 2021

DOI: 10.1007/978-3-030-68211-8_5
Trichotomy for the reconfiguration problem of integer linear systems

Kei Kimura, Akira Suzuki

Theoretical Computer Science, Vol. 856, pp. 88-109, 2021

DOI: 10.1016/j.tcs.2020.12.025
Market pricing for matroid rank valuations

Kristof Berczi, Naonori Kakimura, Yusuke Kobayashi

SIAM Journal on Discrete Mathematics, Vol. 35, pp. 2662-2678, 2021

DOI: 10.1137/20M1386335
Constant amortized time enumeration of eulerian trails

Kazuhiro Kurita, Kunihiro Wasa

arXiv 2101.10473, 2021

DOI: 10.48550/arXiv.2101.10473
Computing the largest bond and the maximum connected cut of a graph

Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza

Algorithmica, Vol. 83, pp. 1421-1458, 2021

DOI: 10.1007/s00453-020-00789-1
Approximability of the independent feedback vertex set problem for bipartite graphs

Yuma Tamura, Takehiro Ito, Xiao Zhou

Theoretical Computer Science, Vol. 849, pp. 227-236, 2021

DOI: 10.1016/j.tcs.2020.10.026
An improved deterministic parameterized algorithm for cactus vertex deletion

Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi

arXiv 2012.04910, 2020

DOI: 10.48550/arXiv.2012.04910
Fixed-parameter algorithms for graph constraint logic

Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki

arXiv 2011.10385, 2020

DOI: 10.48550/arXiv.2011.10385
A note on exponential-time algorithms for linearwidth

Yasuaki Kobayashi, Yu Nakahata

arXiv 2010.02388, 2020

DOI: 10.48550/arXiv.2010.02388
LA/EATCS-Japan発表論文賞

川原純 (京都大学)

「ZDDを用いた組合せ遷移ソルバーについての考察」

著者：伊藤健洋 (東北大学)，川原純 (京都大学)，宋剛秀 (神戸大学)，鈴木顕 (東北大学)，照山順一 (兵庫県立大学)，戸田貴久 (電気通信大学)

2022年2月3日受賞
FIT2020 船井ベストペーパー賞

岡本吉央 (電気通信大学)，伊藤健洋 (東北大学)，垣村尚徳 (慶應義塾大学)，神山直之 (九州大学)，小林佑輔 (京都大学)

「構造変化に応じるロバスト修復可能マトロイド基問題に対する固定パラメータアルゴリズム」
2021年8月26日受賞
2020年度人工知能学会研究会優秀賞

土中哲秀 (中央大学)，小林靖明 (京都大学)，栗田和宏 (国立情報学研究所)，大舘陽太 (名古屋大学)

「多様な部分グラフを発見するアルゴリズム」

2021年6月21日受賞 (所属は研究会発表当時)
第9回藤原洋数理科学賞奨励賞

小林佑輔 (京都大学)

「離散最適化問題に対する効率的アルゴリズムの研究」

2020年10月17日受賞

主な成果

Submodular reassignment problem for reallocating agents to tasks with synergy effects

The Alon-Tarsi number of K5-minor-free graphs

Covering projective planar graphs with three forests

Parameterized complexity of (A, l)-path packing

Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model

A forbidden pair for connected graphs to have spanning k-trees

Independent set reconfiguration on directed graphs

Reconfiguration of regular induced subgraphs

Path cover problems with length cost

Happy set problem on subclasses of co-comparability graphs

Reconfiguration of spanning trees with degree constraint or diameter constraint

An O(n^2)-time algorithm for computing a max-min 3-dispersion on a point set in convex position

Multi-pass streaming algorithms for monotone submodular function maximization

Finding shortest non-separating and non-disconnecting paths

Sorting balls and water: equivalence and computational complexity

A framework to design approximation algorithms for finding diverse solutions in combinatorial problems

An approximation algorithm for k-best enumeration of minimal connected edge dominating sets with cardinality constraints

Reconfiguration of spanning trees with degree constraint or diameter constraint

On the security number of the Cartesian product of graphs

Distributed reconfiguration of spanning trees

Reconfiguration of regular induced subgraphs

Efficient enumeration of dominating sets for sparse graphs

Low-congestion shortcut and graph parameters

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

Computational complexity of jumping block puzzles

Reconfiguring directed trees in a digraph

Decremental optimization of vertex-coloring under the reconfiguration framework

Proper colorings of plane quadrangulations without rainbow faces

Locating evacuation centers optimally in path and cycle networks

日本応用数理学会 第18回若手優秀講演賞

Dynamic bipartite matching market with arrivals and departures

Max-min 3-dispersion problems

On the complexity of fair house allocation

On 3-polytopes with non-Hamiltonian prisms

Color number of cubic graphs having spanning tree with bounded number of leaves

2-Factors of cubic bipartite graphs

Longest common subsequence in sublinear space

ClusterSets: Optimizing planar clusters in categorical point data

A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

A (probably) optimal algorithm for bisection on bounded-treewidth graphs

Finding diverse trees, paths, and more

Polynomial-delay enumeration of large maximal matchings

Algorithms for gerrymandering over graphs

A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with $2 \time 2$ submatrices

Exploring the gap between treedepth and vertex cover through vertex integrity

A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with $2 \times 2$ submatrices

Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

Optimal reconfiguration of optimal ladder lotteries

Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights

Trichotomy for the reconfiguration problem of integer linear systems

Market pricing for matroid rank valuations

Constant amortized time enumeration of eulerian trails

Computing the largest bond and the maximum connected cut of a graph

Approximability of the independent feedback vertex set problem for bipartite graphs

An improved deterministic parameterized algorithm for cactus vertex deletion

Fixed-parameter algorithms for graph constraint logic

A note on exponential-time algorithms for linearwidth

LA/EATCS-Japan発表論文賞

FIT2020 船井ベストペーパー賞

2020年度 人工知能学会 研究会優秀賞

第9回藤原洋数理科学賞奨励賞

日本応用数理学会第18回若手優秀講演賞

2020年度人工知能学会研究会優秀賞