caa a22 4500 445839813 CHVBK 20180317145340.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00186-011-0346-5 doi (NATIONALLICENCE)springer-10.1007/s00186-011-0346-5 Inverse p -median problems with variable edge lengths [Elektronische Daten] [Fahimeh Baroughi Bonab, Rainer Burkard, Elisabeth Gassner] 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 $${\mathcal{NP}}$$-hard on general graphs and weakly $${\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. Springer-Verlag, 2011 Location problem nationallicence Inverse optimization nationallicence p -median nationallicence Complexity analysis nationallicence Baroughi Bonab Fahimeh Department of Applied Mathematics, Sahand University of Technology, Tabriz, Iran aut Burkard Rainer Institute of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010, Graz, Austria aut Gassner Elisabeth Institute of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010, Graz, Austria aut Mathematical Methods of Operations Research Springer-Verlag 73/2(2011-04-01), 263-280 1432-2994 73:2<263 2011 73 186 https://doi.org/10.1007/s00186-011-0346-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00186-011-0346-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Baroughi Bonab Fahimeh Department of Applied Mathematics, Sahand University of Technology, Tabriz, Iran aut NATIONALLICENCE 700 1- Burkard Rainer Institute of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010, Graz, Austria aut NATIONALLICENCE 700 1- Gassner Elisabeth Institute of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010, Graz, Austria aut NATIONALLICENCE 773 0- Mathematical Methods of Operations Research Springer-Verlag 73/2(2011-04-01), 263-280 1432-2994 73:2<263 2011 73 186 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer