id: 05975603 dt: j an: 05975603 au: Alizadeh, Behrooz; Burkard, Rainer E. ti: Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees. so: Networks 58, No. 3, 190-200 (2011). py: 2011 pu: John Wiley \& Sons, Inc., New York, NY la: EN cc: ut: network center location; inverse optimization; combinatorial optimization; design of algorithms ci: li: doi:10.1002/net.20427 ab: Summary: In an inverse network absolute (or vertex) 1-center location problem the parameters of a given network, like edge lengths or vertex weights, have to be modified at minimum total cost such that a prespecified vertex s becomes an absolute (or a vertex) 1-center of the network. In this article, the inverse absolute and vertex 1-center location problems on unweighted trees with \$n + 1\$ vertices are considered where the edge lengths can be changed within certain bounds. For solving these problems, a fast method is developed for reducing the height of one tree and increasing the height of a second tree under minimum cost until the heights of both trees become equal. Using this result, a combinatorial \$O(n^{2})\$ time algorithm is stated for the inverse absolute 1-center location problem in which no topology change occurs. If topology changes are allowed, an \$O(n^{2}\$r) time algorithm solves the problem where \$r,\, r < n\$, is the compressed depth of the tree network \$T\$ rooted in \$s\$. Finally, the inverse vertex 1-center problem with edge length modifications is solved on \$T\$. If all edge lengths remain positive, this problem can be solved within the improved \$O(n^{2})\$ time complexity by balancing the height of two trees. In the general case, one gets the improved \$O(n^{2}r_{v})\$ time complexity where the parameter \$r_{v}\$ is bounded by \$n\$. rv: