On the Solution Value of the Continuous p-Center Location Problem on a Graph
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.
- A finite algorithm for the continuous p-center location problem on a graph
- The continuousm-center problem on a network
- scientific article; zbMATH DE number 849074
- scientific article; zbMATH DE number 5205606
- The p-center location problem in an area
- A heuristic for the p-center problem in graphs
- An improved algorithm for the p-center problem on interval graphs with unit lengths
- The complete vertex \(p\)-center problem
- A new formulation and resolution method for the p-center problem
- scientific article; zbMATH DE number 4141774
- Closed 3-stop center and periphery in graphs
- A finite algorithm for the continuous p-center location problem on a graph
- scientific article; zbMATH DE number 3961341 (Why is no real title available?)
- On alternativep-center problems
- scientific article; zbMATH DE number 468643 (Why is no real title available?)
- Continuous facility location on graphs
- A note on the p-center problem
- Fighting terrorism: how to position rapid response teams?
- Approximating -covering
- Independence and domination on bounded-treewidth graphs: integer, rational, and irrational distances
- The continuous center set of a network
- The absolute centre of a graph
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)