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: