Up- and downgrading the 1-center in a network Gassner, Elisabeth

User activity

Share to:
View the summary of this work
Gassner, Elisabeth
Appears In
European Journal of Operational Research
Algorithms; Business, general; Business, international
Academic; Trade
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.09.013 Byline: Elisabeth Gassner Keywords: Combinatorial optimization; Location problem; Vertex center; Upgrading; Downgrading; Network improvement; Network modification; Complexity; Tree Abstract: We study budget constrained network improvement and degrading problems based on the vertex 1-center problem on graphs: given a graph with vertex weights and edge lengths the task is to decrease and increase the vertex weights within certain limits such that the optimal 1-center objective value with respect to the new weights is minimized and maximized, respectively. The upgrading (improvement) problem is shown to be solvable in O(n.sup.2) time provided that the distance matrix is given. The downgrading 1-center problem is shown to be strongly NP-hard on general graphs but can be solved in O(n.sup.2) time on trees. As byproduct we suggest an algorithm that solves the problem of minimizing over the upper envelope of n piecewise linear functions in O(K+n) time where K is the total number of breakpoints. Author Affiliation: Department of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, A-8010 Graz, Austria Article History: Received 17 July 2007; Accepted 17 September 2008
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users