On the Solution Value of the Continuous <i>p</i>-Center Location Problem on a Graph (Q3758534)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4008072
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the Solution Value of the Continuous <i>p</i>-Center Location Problem on a Graph |
scientific article; zbMATH DE number 4008072 |
Statements
On the Solution Value of the Continuous <i>p</i>-Center Location Problem on a Graph (English)
0 references
1987
0 references
network location
0 references
continuous p-center problem
0 references
graph
0 references
Euler tour
0 references
r- covering
0 references
0.9438763
0 references
0.9010279
0 references
0.8833038
0 references
0.8803221
0 references
0.87382406
0 references
0.87186766
0 references
0.8711414
0 references
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.
0 references