|
Given a simple graph G=(V, E), a vertex v \in V is said to
dominate itself and all vertices u in V which are adjacent to v.
A subset D of V is called an efficient dominating set of G if
every vertex in V is dominated by exactly one vertex in D. The
efficient domination problem is to find an efficient dominating
set of G with the minimum cardinality. Suppose that each vertex
v in V is associated with a real number. Then, the weighted
efficient domination problem is to find an efficient dominating
set with the minimum weight in G. There are many interesting
applications for efficient domination in coding theory, graph
embedding, facility location on geographical area and resource
allocation in parallel processing system. It is well known that
the efficient domination problem is NP-complete for bipartite
graphs, chordal graphs and planar graphs of maximum degree
three. Much research has been devoted to investigating the
algorithmic complexity of the weighted efficientdomination
problem on other special classes of graphs, such as trees,
series-parallel graphs, split graphs, block graphs, interval
graphs, cocomparability graphs and circular-arc graphs. In this
dissertation, we show that the efficient domination problem is
NP-complete when restricted to planar bipartite graphs, the line
graphs of planar bipartite graphs and chordal bipartite graphs.
For the weighted efficient domination problem, we present an O(
|V|) time algorithm on bipartite permutation graphs,an O(|V|+|E''
|) time algorithm on permutation graphs, an O(|V|loglog|V|+|E''|)
time algorithm on trapezoid graphs and an O(|V|) time algorithm
on distance-hereditary graphs,where |E''| denotes the number of
edges in the complement of G.On the other hand, we also
investigate the algorithmic complexity of the edge version
problem of efficient domination in graphs. The efficient edge
domination problem on general graphs has been shown to be NP-
complete, but can be solved in linear time when restricted to
generalized series-parallel graphs and interval graphs. As to
the weighted version of this problem, few work has been
published. In this dissertation, we prove that the efficient
edge domination problem is NP-complete when restricted to planar
bipartite graphs and hence it remains NP-complete on any
superclass of planar bipartite graphs, e.g., planar graphs and
bipartite graphs. In addition, we present O(|V|+|E|) time
algorithms to solve the weighted efficient edge domination
problem on bipartite permutation graphs, generalized series-
parallel graphs and chordal graphs. It is worth mentioning that
on chordal graphs, the weighted efficient domination problem is
NP-complete, but the weighted efficient edge domination is
linear time solvable.
|