direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 705-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

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(n3) 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} + n2), O( m}3/2 + n2), and O(n2.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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe