Thesis (PhD)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The (classical) domination number of a graph is the cardinality of a smallest subset of its vertex
set with the property that each vertex of the graph is in the subset or adjacent to a vertex in the
subset. Since its introduction to the literature during the early 1960s, this graph parameter has
been researched extensively and nds application in the generic facility location problem where
a smallest number of facilities must be located on the vertices of the graph, at most one facility
per vertex, so that there is at least one facility in the closed neighbourhood of each vertex of the
graph.
The placement constraint in the above application may be relaxed in the sense that multiple
facilities may possibly be located at a vertex of the graph and the adjacency criterion may be
strengthened in the sense that a graph vertex may possibly be required to be adjacent to multiple
facilities. More speci cally, the number of facilities that can possibly be located at the i-th vertex
of the graph may be restricted to at most ri 0 and it may be required that there should be at
least si 0 facilities in the closed neighbourhood of this vertex. If the graph has n vertices, then
these restriction and su ciency speci cations give rise to a pair of vectors r = [r1,....., rn] and
s = [s1,....., sn]. The smallest number of facilities that can be located on the vertices of a graph
satisfying these generalised placement conditions is called the hr; si-domination number of the
graph. The classical domination number of a graph is therefore its hr; si-domination number in
the special case where r = [1,....., 1] and s = [1,....., 1].
The exact values of the hr; si-domination number, or at least upper bounds on the hr; si-
domination number, are established analytically in this dissertation for arbitrary graphs and
various special graph classes in the general case, in the case where the vector s is a step function
and in the balanced case where r = [r,....., r] and s = [s,....., s].
A linear algorithm is put forward for computing the hr; si-domination number of a tree, and
two exponential-time (but polynomial-space) algorithms are designed for computing the hr; si-
domination number of an arbitrary graph. The e ciencies of these algorithms are compared
to one another and to that of an integer programming approach toward computing the hr; si-
domination number of a graph. / AFRIKAANSE OPSOMMING: Die (klassieke) dominasiegetal van 'n gra ek is die grootte van 'n kleinste deelversameling van
die gra ek se puntversameling met die eienskap dat elke punt van die gra ek in die deelversameling
is of naasliggend is aan 'n punt in die deelversameling. Sedert die verskyning van hierdie
gra ekparameter in the literatuur gedurende die vroeë 1960s, is dit deeglik nagevors en vind dit
neerslag in die generiese plasingstoepassing waar 'n kleinste getal fasiliteite op die punte van die
gra ek geplaas moet word, hoogstens een fasiliteit per punt, sodat daar minstens een fasiliteit in
die geslote buurpuntversameling van elke punt van die gra ek is.
Die plasingsbeperking in die bogenoemde toepassing mag egter verslap word in die sin dat
meer as een fasiliteit potensieel op 'n punt van die gra ek geplaas kan word en verder mag
die naasliggendheidsvereiste verhoog word in die sin dat 'n punt van die gra ek moontlik aan
veelvuldige fasiliteite naasliggend moet wees. Gestel dat die getal fasiliteite wat op die i-de punt
van die gra ek geplaas mag word, beperk word tot hoogstens ri 0 en dat hierdie punt minstens
si 0 fasiliteite in die geslote buurpuntversameling daarvan moet hê. Indien die gra ek n punte
bevat, gee hierdie plasingsbeperkings en -vereistes aanleiding tot die paar vektore r = [r1, .... , rn]
en s = [s1,...., sn]. Die kleinste getal fasiliteite wat op die punte van 'n gra ek geplaas kan word
om aan hierdie veralgemeende voorwaardes te voldoen, word die hr; si-dominasiegetal van die
gra ek genoem. Die klassieke dominasiegetal van 'n gra ek is dus die hr; si-dominasiegetal
daarvan in die spesiale geval waar r = [1,......, 1] en s = [1,....., 1].
In hierdie verhandeling word die eksakte waardes van, of minstens grense op, die hr; si-dominasiegetal
van arbitrêre gra eke of spesiale klasse gra eke analities bepaal vir die algemene geval,
vir die geval waar s 'n trapfunksie is, en vir die gebalanseerde geval waar r = [r,....., r] en
s = [s,....., s].
'n Lineêre algoritme word ook daargestel vir die berekening van die hr; si-dominasiegetal van
'n boom, en twee eksponensiële-tyd (maar polinoom-ruimte) algoritmes word ontwerp vir die
berekening van die hr; si-dominasiegetal van 'n arbitrêre gra ek. Die doeltre endhede van hierdie
algoritmes word met mekaar vergelyk en ook met dié van 'n heeltallige programmeringsbenadering
tot die bepaling van die hr; si-dominasiegetal van 'n gra ek.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/86266 |
| Date | 04 1900 |
| Creators | Roux, Adriana |
| Contributors | Van Vuuren, J. H., Stellenbosch University. Faculty of Economics and Management Sciences. Dept. of Logistics. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | 143 p. |
| Rights | Stellenbosch University |
Page generated in 0.0018 seconds