2010/12/22 by Behrooz Alizadeh, R.E. Burkard, Rainer E. Burkard
Business, Management and Accounting · Computer Science · Mathematics · #Algorithm #Bounded function #Center (category theory) #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Facility Location and Emergency Management #Geometry #Graph #Inverse #Mathematics #Network topology #Time complexity #Tree network #Vertex (graph theory)
paper · doi:10.1002/net.20427
crossref issued 2010/12/22 · crossref published 2010/12/22 · crossref published-online 2010/12/22 · openalex publication_date 2010/12/22 · crossref created 2010/12/22 · crossref published-print 2011/10/01 · crossref deposited 2023/10/09 · openalex created_date 2025/10/10 · crossref indexed 2026/07/30 · openalex updated_date 2026/07/30
Abstract 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