Vertex partitioning of crown-free interval graphs (Q4944995)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1420923
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Vertex partitioning of crown-free interval graphs |
scientific article; zbMATH DE number 1420923 |
Statements
20 January 2003
0 references
crown-free interval graphs
0 references
0.7707030177116394
0 references
0.770222544670105
0 references
0.7679708003997803
0 references
0.7520272135734558
0 references
Vertex partitioning of crown-free interval graphs (English)
0 references
Bewiesen wird eine approximative Lösung der Färbung gewisser linearer Intervall-Mengen mit Hilfe beschreibender Graphen. Dazu werden bestimmte Partitionierungen der Graphen ohne Subgraph \(K[1,1,3]\) (``Krone''), welche einer Menge von Intervallen einer linear geordneten Menge entsprechen: Partitionierungen P, welche durch geordnete Folge von maximalen Sippen \(C[q]\) (cliques: Subgraphen entsprechend der Intervall-Ordnung) derart erzeugt werden, sodass P jeden Eckpunkt genau einmal überdeckt. Existenz wird durch algorithmische Konstruktion bewiesen. Stets ist P so möglich, dass jeder (gerichtete) Weg in höchstens vier Sippen von P erscheint. Bei Anwenden auf Intervall-Färbung von (Intervall-)Graphen ohne und mit Eckpunkt-Gewichten folgt daraus Existenz eines ``4-Approximations-Algorithmus'' und so eine approximative Lösung dieses allgemein NP-harten Färbungsproblems für Mengen mit den genannten Kronenfreien Graphen. For the entire collection see [Zbl 0929.00074].
0 references