論文・受賞| 組合せ遷移＠学術変革領域研究(B)

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

論文・受賞

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

On the security number of the Cartesian product of graphs

Distributed reconfiguration of spanning trees

Efficient enumeration of dominating sets for sparse graphs

Low-congestion shortcut and graph parameters

Computational complexity of jumping block puzzles

Reconfiguring directed trees in a digraph

Decremental optimization of vertex-coloring under the reconfiguration framework