Recognizing Graphs without Asteroidal Triples

not available

graph, algorithm, asteroidal triple-free, AT-free, recognition

We consider the problem of recognizing AT-free graphs. Although there is a simple O(n³) algorithm, no faster method for solving this problem had been known. Here we give three different algorithms which have a better time complexity for graphs which are sparse or have a sparse complement; in particular we give algorithms which recognize AT-free graphs in O(n m} + n²), O( m}^3/2 + n²), and O(n^2.82 + n m). In addition we give a new characterization of graphs with bounded asteroidal number by the help of the knotting graph, a combinatorial structure which was introduced by Gallai for considering comparability graphs.

Download as [PDF] [ps.gz]