Name
Abstract | ||
|---|---|---|
An independent set fx; y; zg is called an asteroidal triple if between any pair in thetriple there exists a path that avoids the neighborhood of the third. A graph is referredto as AT-free if it does not contain an asteroidal triple. We present a simple linear-timealgorithm to compute a dominating path in a connected AT-free graph.Keywords. asteroidal triple-free graphs, domination, algorithms1 IntroductionA number of families of graphs including interval graphs [10], permutation... |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0020-0190(95)00021-4 | Inf. Process. Lett. |
Keywords | Field | DocType |
linear time algorithm,at-free graph,dominating path,independent set,interval graph,algorithms | Strength of a graph,Discrete mathematics,Dominating set,Combinatorics,Line graph,Cubic graph,Algorithm,Distance-hereditary graph,Mathematics,Voltage graph,Path graph,Complement graph | Journal |
Volume | Issue | ISSN |
54 | 5 | 0020-0190 |
Citations | PageRank | References |
17 | 1.81 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Derek G. Corneil | 1 | 1397 | 218.67 |
| Stephan Olariu | 2 | 2252 | 166.46 |
| Lorna Stewart | 3 | 361 | 28.05 |