Name
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.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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1137/S0097539795282377 | SIAM J. Comput. |
Keywords | Field | DocType |
linear time algorithms,asteroidal triple-free graphs,connected at-free graph,dominating pair,at-free graph,best algorithm,asteroidal triple-free,extended algorithm,simple algorithm,cocomparability graph,dominating pairs,lexicographic breadth- rst search,input graph g,dominating set,algorithms,lexicographic breadth first search,independent set | Permutation graph,Discrete mathematics,Dominating set,Combinatorics,Algorithm,Distance-hereditary graph,Independent set,Pathwidth,Mathematics,Trapezoid graph,Maximal independent set,Complement graph | Journal |
Volume | Issue | ISSN |
28 | 4 | 0097-5397 |
ISBN | Citations | PageRank |
3-540-60084-1 | 48 | 3.94 |
References | Authors | |
15 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Derek G. Corneil | 1 | 1397 | 218.67 |
| Stephan Olariu | 2 | 444 | 56.26 |
| Lorna Stewart | 3 | 361 | 28.05 |
| DG Corneil | 4 | 48 | 3.94 |