On the Solution Value of the Continuous p-Center Location Problem on a Graph

From MaRDI portal
Publication:3758534





The continuous (or absolute) p-center problem on a graph (considered here as a network, i.e. points may lie at vertices or on arcs and arcs have a length) concerns finding p points (centers) on the graph so as to minimize the distance of any point to the nearest center. The solution value \(r_ p\) is thus the smallest r for which the graph may be covered by p spheres of radius r. It is shown that \(r_ p\) is always of the form T/2q where q is an integer at most 2p, and T stands for the length of an Euler tour of a subgraph of following type: two disjoint cycles connected by a path, in which the cycle(s) and/or the path are allowed to be degenerate. For general graphs with integer arclengths the set of possible values of \(r_ p\) thus consists of at most 4pd rationals, where d is the graph's total length. \(r_ p\) may then be found by solving r-covering problems for O(log p\(+\log d)\) values of r. For some special classes of graph even better bounds on this number of r- covering problems may be obtained. It must be added that a polynomial algorithm for the r-covering problem is known only for those graphs in which each nontrivial biconnected component is either a cycle or a cycle with one chord.











This page was built for publication: On the Solution Value of the Continuous p-Center Location Problem on a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758534)