Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA 2016) 18-32 2016年 [査読有り]
A dynamic network introduced by Ford and Fulkerson is a directed graph with capacities and transit times on its arcs. The quickest transshipment problem is one of the most fundamental problems in dynamic networks. In this problem, we are given sou...
In this paper, we characterize the redundant rigidity and the redundant global rigidity of body-hinge graphs in R-d in terms of graph connectivity. Although an efficient algorithm which determines mixed-connectivity is still not known, our result ...
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...
This paper considers the k-sink location problem in dynamic path networks. A dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. A path can be considered as a road, e...
This paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is non...