The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-Free Graphs
Derek G. Corneil, Stephan Olariu, Lorna Stewart,
Pages. 1284-1297
Abstract An independent set of three vertices is called an $asteroidal ; triple$ if
between each pair in the triple there exists a path that avoids the neighborhood
of the third. A graph is asteroidal triple- free (AT-free) if it contains no
asteroidal triple. The motivation for this investigation is provided, in part,
by the fact that AT-free graphs offer a common generalization of interval,
permutation, trapezoid, and cocomparability graphs.
indent Previously, the authors have given an existential proof of the fact that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. The main contribution of
this paper is a constructive proof of the existence of dominating pairs in
connected AT-free graphs. The resulting simple algorithm, based on the
well-known lexicographic breadth-first search, can be implemented to run in time
linear in the size of the input, whereas the best algorithm previously known for
this problem has complexity $O(|V|^3)$ for input graph $G=(V,E)$. In addition,
we indicate how our algorithm can be extended to find, in time linear in the
size of the input, all dominating pairs in a connected AT-free graph with
diameter greater than 3. A remarkable feature of the extended algorithm is that,
even though there may be $O(|V|^2)$ dominating pairs, the algorithm can compute
and represent them in linear time.
Contents 1. Introduction
2. Background
3. Lexicographic breadth-fist search
4. The dominating pair algorithm
5. Computing dominated sets
6. Computing all dominating pairs
7. Conclusions
Key words lgorithms, dominating pairs, asteroidal triple-free graphs, lexicographic breadth-first search
Mathmatical Subject Classification 05C85, 68R10