TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1993

Finiteness Theorems for Graphs and Posets Obtained by Compositions
Zitatschlüssel Report-351-1993
Autor Jens Gustedt
Jahr 1993
Nummer 351
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it. In particular we show that the following classes have infinite antichains with resp. to the induced subgraph/poset relation: interval graphs and orders, $N$-free orders, orders with bounded decomposition width\/. On the other hand for orders with bounded decomposition diameter\/ finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe