Premium
Combinatorial algorithms for inverse absolute and vertex 1‐center location problems on trees
Author(s) -
Alizadeh Behrooz,
Burkard R.E.
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20427
Subject(s) - vertex (graph theory) , inverse , mathematics , combinatorics , bounded function , center (category theory) , algorithm , network topology , tree network , time complexity , discrete mathematics , computer science , graph , geometry , mathematical analysis , chemistry , crystallography , operating system
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 . © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(3), 190–200 2011