7 citations · 17 across the 16 of their papers we have counts for
17 papers
Connected domination in grid graphs
Masahisa Goto, Koji M. Kobayashi
Given an undirected simple graph, a subset of the vertices of the graph is a {\em dominating set} if every vertex not in the subset is adjacent to at least one vertex in the subset…
An optimal algorithm for 2-bounded delay buffer management with lookahead
Koji M. Kobayashi
The bounded delay buffer management problem, which was proposed by Kesselman et~al.\ (STOC 2001 and SIAM Journal on Computing 33(3), 2004), is an online problem focusing on buffer…
Online interval scheduling to maximize total satisfaction
Koji M. Kobayashi
The interval scheduling problem is one variant of the scheduling problem. In this paper, we propose a novel variant of the interval scheduling problem, whose definition is as follo…
Improved Bounds for Online Dominating Sets of Trees
Koji M. Kobayashi
The online dominating set problem is an online variant of the minimum dominating set problem, which is one of the most important NP-hard problems on graphs. This problem is defined…
A tight analysis of Kierstead-Trotter algorithm for online unit interval coloring
Tetsuya Araki, Koji M. Kobayashi
Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for the online interval coloring problem. In this paper, for onli…
An improved lower bound for one-dimensional online unit clustering
Jun Kawahara, Koji M. Kobayashi
The online unit clustering problem was proposed by Chan and Zarrabi-Zadeh (WAOA2007 and Theory of Computing Systems 45(3), 2009), which is defined as follows: "Points" are given on…