zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
On conditional covering problem. (English) Zbl 1205.05229
Summary: The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by J. A. Horne and J. C. Smith [Networks 46, No. 4, 177–185 (2005; Zbl 1093.90072)]. We show that their algorithm is wrong and further present a correct O(n 3 ) algorithm for the same. We also propose an O(n 2 ) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.
MSC:
05C85Graph algorithms (graph theory)
05C69Dominating sets, independent sets, cliques
05C70Factorization, etc.
90C39Dynamic programming
90B80Discrete location and assignment
References:
[1]Chaudhry S.S., Moon I.D., McCormick S.T.: Conditional covering: greedy heuristics and computational results. Comput. OR 14(1), 11–18 (1987) · Zbl 0622.90060 · doi:10.1016/0305-0548(87)90053-0
[2]Goldberg J.B., Lunday B.J., Smith J.C.: Algorithms for solving the conditional covering problem on paths. Naval Res. Logist. 52(4), 293–301 (2005) · Zbl 1090.90123 · doi:10.1002/nav.20074
[3]Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
[4]Horne J.A., Smith J.C.: A dynamic programming algorithm for the conditional covering problem on tree graphs. Networks 46(4), 186–197 (2005) · Zbl 1093.90073 · doi:10.1002/net.20087
[5]Horne J.A., Smith J.C.: Dynamic programming algorithms for the conditional covering problem on path and extended star graphs. Networks 46(4), 177–185 (2005) · Zbl 1093.90072 · doi:10.1002/net.20086
[6]Kratsch D.: Domination and total domination on asteroidal triple-free graphs. Discrete Appl. Math. 99(1–3), 111–123 (2000) · Zbl 0943.05063 · doi:10.1016/S0166-218X(99)00128-6
[7]Moon I.D., Chaudhry S.S.: An analysis of network location problems with distance constraints. Manage. Sci. 30, 290–307 (1984) · Zbl 0553.90034 · doi:10.1287/mnsc.30.3.290
[8]Moon I.D., Papayanopoulos L.: Facility location on a tree with maximum distance constraints. Comput. OR 22(9), 905–914 (1995) · Zbl 0854.90091 · doi:10.1016/0305-0548(94)00079-N
[9]Pfaff J., Laskar R., Hedetniemi S.T.: Linear algorithms for independent domination and total domination in series-parallel graphs. Manage. Sci. 30, 290–307 (1984) · Zbl 0553.90034 · doi:10.1287/mnsc.30.3.290