Premium
A linear time algorithm for the reverse 1‐median problem on a cycle
Author(s) -
Burkard Rainer E.,
Gassner Elisabeth,
Hatzl Johannes
Publication year - 2006
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.20115
Subject(s) - bipartite graph , vertex (graph theory) , mathematics , algorithm , combinatorics , graph , constant (computer programming) , computer science , discrete mathematics , mathematical optimization , programming language
This article deals with the reverse 1‐median problem on graphs with positive vertex weights. The problem is proved to be strongly N P ‐hard even in the case of bipartite graphs and not approximable within a constant factor (unless P = N P ). Furthermore, a linear time algorithm for the reverse 1‐median problem on a cycle with linear cost functions (RMC) is developed. It is also shown that there exists an integral optimal solution of RMC if the input data are integral. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 16‐23 2006