direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 704-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

AT-free, coAT-free Graphs and AT-free Posets
not available
graph, algorithm, asteroidal triple-free, AT-free, minimal separator
In this extended abstract we consider structural and algorithmic properties of two graph classes which share the property that they are on the one hand generalizations of permutation graphs, on the other hand subfamilies of AT-free graphs.
First we consider graphs that are AT-free and coAT-free. We show that the number of minimal separators in an AT-free, coAT-free graph is bounded by a polynomial in the number of vertices of the graph. From this it follows that problems like treewidth}, pathwidth}, minimum fill-in}, minimum interval graph completion}, and vertex ranking} become solvable in polynomial time for AT-free, coAT-free graphs.
The second part of the paper is devoted to AT-free posets, i.e. comparability graphs not containing an asteroidal triple. We study the relationship between dominating pair vertices and extremal elements (i.e. minimal or maximal elements) of a given AT-free poset. Furthermore we suggest an ordering for posets that visualizes the overall structure of AT-free posets.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe