direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1990

A 3/2-Approximation Algorithm for the Jump Number of Interval Orders
Zitatschlüssel Report-220-1989
Autor Stefan Felsner
Seiten 325-334
Jahr 1989
Journal ORDER, 1990
Jahrgang 6
Nummer 220
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung The jump number of a partial order $P$ is the minimum number of incomparable adjacent pairs in some linear extension of $P$. The jump number is known to be NP-hard in general. However some particular classes of posets admit easy calculation of the jump number. The complexity status for interval orders still remains unknown. Here we present an algorithm that, given an interval order $P$, generates a linear extension Λ, whose jump number is less than $\frac32$ times the jump number of $P$.
Typ der Publikation Preprint
Download Bibtex Eintrag