Universitšt Oldenburg
Fachbereich Informatik

Publications: Details


Document Description

Author: Günther Stiege
Title: Knuth Graphs
Kind of Publication: Report. Berichte aus dem Department für Informatik 02/15, Universität Oldenburg, December 2015
Date: December 2015
Institution: Universitšt Oldenburg; Graphen und Netzwerke
Pages, Language 23 English
Keywords: Knuth graph, clique decomposition, vertex coloring
CR Classification: E.1 [Data structures] (Graphs and networks)
General Terms (ACM): Algorithms
up

Abstract

Knuth's graphs are charcterized by line-disjoint cliques. An efficient algorithm allows finding the clique decomposition of Knuth graphs. A Knuth graph is perfect if its complement is a Knuth graph. Vertex coloring of Knuth graphs is NP-complete. Vertex coloring of the complements of Knuth can be done in polynomial time.

Kurzfassung

Knuth-Graphen sind durch liniendisjunkte Cliquen charakterisiert. Es existiert ein effizienter Algorithmus zu Bestimmung von Knuth-Graphen. Ein Knuth Graph ist genau dann perfekt, wenn sein Komplement ein Knuth-Graph ist. Knotenfärbung von Knuth-Graphen ist NP-vollständig. Knotenfärbung der Komplemente von Knuth-Graphen ist in polynomieller Zeit möglich.

up

Download

up

Remarks

None.
up


Last change: 2007/06/17 (Stiege)