Tadashi Sakuma

dblp:63/1890 · DBLP profile ↗
← Back
9ranked-venue papers
2as first author
1since 2021 · last 2022
0000-0001-6925-252XORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 7 · 2 first-author · 1 since 2021Artificial intelligence and machine learning · 1Computer networks · 1
YearPublicationVenuePosition
2022 On the average hitting times of the squares of cycles
Yoshiaki Doi, Norio Konno, Tomoki Nakamigawa, Tadashi Sakuma, Etsuo Segawa, Hidehiro Shinohara, Shunya Tamura, Yuuho Tanaka, Kosuke Toyota
Discret. Appl. Math.4
2020 Stable Structure on Safe Set Problems in Vertex-Weighted Graphs II -Recognition and Complexity-
Shinya Fujita 0001, Boram Park, Tadashi Sakuma
WG3
2018 Safe sets, network majority on weighted trees
abstract
Let be a graph and let be a positive weight function on the vertices of G. For every subset X of V, let . A non‐empty subset is a weighted safe set if, for every component C of the subgraph induced by S and every component D of , we have whenever there is an edge between C and D. If the subgraph induced by a weighted safe set S is connected, then the set S is called a weighted connected safe set. In this article, we show that the problem of computing the minimum weight of a safe set is ‐hard for trees, even if the underlying tree is restricted to be a star, but it is polynomially solvable for paths. We also give an time 2‐approximation algorithm for finding a weighted connected safe set with minimum weight in a weighted tree. Then, as a generalization of the concept of a minimum safe set, we define the concept of a parameterized infinite family of proper central subgraphs on weighted trees, whose polar ends are the vertex set of the tree and the centroid points. We show that each of these central subgraphs includes a centroid point.
Ravindra B. Bapat 0001, Shinya Fujita 0001, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Tadashi Sakuma, Zsolt Tuza
Networks6
2016 Safe Sets in Graphs: Graph Classes and Structural Parameters
Raquel Águeda, Nathann Cohen, Shinya Fujita 0001, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu
COCOA10
2016 Safe set problem on graphs
Shinya Fujita 0001, Gary MacGillivray, Tadashi Sakuma
Discret. Appl. Math.3
2015 Pebble exchange on graphs
Shinya Fujita 0001, Tomoki Nakamigawa, Tadashi Sakuma
Discret. Appl. Math.3
2001 On kernel-less clique-acyclic orientations of minimally imperfect graphs
Tadashi Sakuma
Discret. Appl. Math.1
2001 Notes on acyclic orientations and the shelling lemma
Komei Fukuda, Alain Prodon, Tadashi Sakuma
Theor. Comput. Sci.3
2000 Forced color classes, intersection graphs and the strong perfect graph conjecture
Tadashi Sakuma
Theor. Comput. Sci.1