|
Let G=(V,E) be a simple graph, m be the number of edges and n
be the number of vertices. The length of a path is the number
of edges in the path. The distance d(x,y) from vertex x to
vertex y in G is the minimum length of a path from x to y. If d(
x,y) is less than or equal to k, then we say that x dominates y
within distance k (or say that x k-dominate y), and vice versa.
A subset D of V is called a k-dominating set of G if for every
vertex x in V, there exists some vertex y in D which k-
dominates x. A k-dominating set D of G is independent if the
vertices of D are pairwise non-adjacent, connected if the sub-
graph G[D] induced by D is connected, toatl if G[D] has no
isolated vertex. The (independent, connected, total) k-
domination problem is to find a (independent, connected, total)
k-dominating set with the minimum cardinality. Suppose that
each vertex of the G is associated with a real number, called
the weight of this vertex, and the weight of a set of vertices
is the sum of the weights of all vertices in this set. Then,
the weighted (independent, connected, total) k-domination
problem is to find a (independent, connected, total) k-
dominating set with the minimum weight in G. A subset M of E is
called a mathcing in G=(V,E) if no two elements of M share the
same vertex. M is a maximum mathcing if G has no mathcing M'
with |M'| > |M|. In this thesis, we use the dynamic programming
to devise unified, efficient and linear time algorithms for the
weighted (independent, connected, total) k-domination problem
on interval graphs. Then, we extend those algorithms to solve
the same pro- blems on circular-arc graphs. Meanwhile, we
present an O(m+n) greedy algorithm for solving the maximum
matching problem in strongly chordal graphs with strong
elimination ordering given.
|