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
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references