Geodesic
Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014 , Tome 18 (2014) no. 4, pp. 539-555.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 a positive value is unknown but only the interval of supply is known. A particular realization of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location x is defined as the minimum time to complete the evacuation to x for all supplies (evacuees), and the regret of x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a sink location which minimizes the maximum regret for all possible scenarios. We present an O(n2 log2 n) time algorithm for the minimax regret sink location problem in dynamic tree networks with uniform capacity, where n is the number of vertices in the network. As a preliminary step for this result, we also address the minimum cost sink location problem in a dynamic tree networks under a fixed scenario and present an O(n logn) time algorithm, which improves upon the existing time bound of O(n log2 n) by if edges of a tree have uniform capacity. 
@article{JGAA_2014_18_4_a3,
     author = {Yuya Higashikawa and Mordecai Golin and Naoki Katoh},
     title = {Minimax {Regret} {Sink} {Location} {Problem} in {Dynamic} {Tree} {Networks} with {Uniform} {Capacity}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {539--555},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2014},
     doi = {10.7155/jgaa.00336},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00336/}
}
TY  - JOUR
AU  - Yuya Higashikawa
AU  - Mordecai Golin
AU  - Naoki Katoh
TI  - Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 539
EP  - 555
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00336/
DO  - 10.7155/jgaa.00336
LA  - en
ID  - JGAA_2014_18_4_a3
ER  - 
%0 Journal Article
%A Yuya Higashikawa
%A Mordecai Golin
%A Naoki Katoh
%T Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity
%J Journal of Graph Algorithms and Applications
%D 2014
%P 539-555
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00336/
%R 10.7155/jgaa.00336
%G en
%F JGAA_2014_18_4_a3
Yuya Higashikawa; Mordecai Golin; Naoki Katoh. Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014
					, Tome 18 (2014) no. 4, pp. 539-555. doi : 10.7155/jgaa.00336. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00336/

Cité par Sources :