Abstract | ||
---|---|---|
)Derek G. CorneilStephan OlariuyLorna StewartzSummary of ResultsAn independent set of three vertices is called an asteroidal triple if between every two vertices inthe triple there exists a path avoiding the neighbourhood of the third. A graph is asteroidal triplefree(AT-free, for short) if it contains no asteroidal triple. A classic result states that a graph is aninterval graph if and only if it is chordal and AT-free. Our main contribution is to exhibit a verysimple,... |
Year | DOI | Venue |
---|---|---|
1998 | 10.1145/314613.314697 | SODA |
Keywords | Field | DocType |
interval graph,independent set | Strength of a graph,Discrete mathematics,Combinatorics,Line graph,Circle graph,Interval graph,Computer science,Simplex graph,Null graph,Butterfly graph,Voltage graph | Conference |
Citations | PageRank | References |
20 | 1.71 | 2 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Derek G. Corneil | 1 | 1397 | 218.67 |
Stephan Olariu | 2 | 444 | 56.26 |
Lorna Stewart | 3 | 361 | 28.05 |