A d-dimensional body-hinge framework is a collection of d-dimensional rigid bodies connected by hinges, where a hinge is a (d - 2)-dimensional affine subspace, i.e., pin-joints in 2-space, line-hinges in 3-space, plane-hinges in 4-space and etc. B...
JOURNAL OF COMBINATORIAL OPTIMIZATION 28(2) 480-495 2014年8月 [査読有り]
This paper deals with online graph exploration problems by multiple searchers. The information on the graph is given online. As the exploration proceeds, searchers gain more information on the graph. Assuming an appropriate communication model amo...
Yuya Higashikawa   Mordecai J. Golin   Naoki Katoh   
ALGORITHMS AND COMPUTATION, WALCOM 2014 8344 125-137 2014年 [査読有り]
This paper addresses the minimax regret sink location problem in dynamic tree networks. In our model, a dynamic tree network consists of an undirected tree with positive edge lengths and uniform edge capacity, and the vertex supply which is nonneg...
COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014) 8881 474-489 2014年 [査読有り]
We consider the bracing problem of a square grid framework possibly with holes and present an efficient algorithm for making the framework infinitesimally rigid by augmenting it with the minimum number of diagonal braces. This number of braces mat...
Yuya Higashikawa   Mordecai J. Golin   Naoki Katoh   
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2014 8546 149-161 2014年 [査読有り]
This paper considers the k-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. Here, each vertex suppl...