A linear time algorithm for the reverse 1‐median problem on a cycle | Zendy

Burkard Rainer E. | Zendy; Gassner Elisabeth | Zendy; Hatzl Johannes | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research