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

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. 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 lgorithms, dominating pairs, asteroidal triple-free graphs, lexicographic breadth-first search 05C85, 68R10