Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017) 10389 133-144 2017年 [査読有り]
We address the problem of locating k sinks on dynamic flow path networks with n vertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run in O(n log n + k2 log4 n) and O(n log3 n) time, respectively. W...
Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC 2017) 334-344 2017年 [査読有り]
In the air-traffic control, the information related to each air-plane needs to be always displayed as the label. Motivated by this appli-cation, de Berg and Gerrits (Comput. Geom. 2012) presented free-label maximization problem, where the goal is to...
DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 9943 24-36 2016年 [査読有り]
We first consider the weighted p-center problem, in which the centers are constrained to lie on two axis-parallel lines. Given a set of n points in the plane, which are sorted according to their x-coordinates, we show how to test in O(n log n) tim...
Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016) 9843 122-134 2016年 [査読有り]
This paper considers the minimax regret 1-median problem in dynamic path networks. In our model, we are given a dynamic path network consisting of an undirected path with positive edge lengths, uniform positive edge capacity, and nonnegative verte...