Constrained pairwise and center-star sequences alignment problems |
| |
Authors: | Yong Zhang Joseph Wun-Tat Chan Francis Y. L. Chin Hing-Fung Ting Deshi Ye Feng Zhang Jianyu Shi |
| |
Affiliation: | 1. Business School, Sichuan University, Chengdu?, 610065, China 2. State Key Lab for Manufacturing Systems Engineering, Xi’an?, 710049, China
|
| |
Abstract: | This paper considers the minimax regret vertex 2-sink location problem in a dynamic path network with positive edge lengths and uniform edge capacity. Let (P) be an undirected path graph of (n) vertices, and the weight (initial supply) of every vertex is known as an interval. The problem is to find two vertices (x) and (y) as two sinks on the path such that all the weights can evacuate to (x) and (y) with minimum regret of evacuation time in case of an emergency for any possible weight distribution. We present an (O(n^3log n)) time algorithm. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|