Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths |
| |
Authors: | Fahimeh Baroughi Bonab Rainer E Burkard Elisabeth Gassner |
| |
Institution: | 1.Department of Applied Mathematics,Sahand University of Technology,Tabriz,Iran;2.Institute of Optimization and Discrete Mathematics,Graz University of Technology,Graz,Austria |
| |
Abstract: | The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given
modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median
problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest
a linear time algorithm. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|