Universitšt Oldenburg
Fachbereich Informatik

Publications: Details


Document Description

Author: Günther Stiege
Title: Playing with Knuth's words.dat
Kind of Publication: Report. Berichte aus dem Department für Informatik 01/12, Universität Oldenburg, May 2012
Date: May 2012
Institution: Universitšt Oldenburg; Graphen und Netzwerke
Pages, Language 59 English
Keywords: Strongly transitive partition, words.dat
CR Classification: E.1 [Data structures] (Graphs and networks)
General Terms (ACM): Algorithms
up

Abstract

Knuth's file words.dat is a large collection of five-letter English words provided with a structure as undirected graph. For this graph a complete biblock decomposition is provided and analyzed. A complete decomposition into cliques is also presented. Since words.dat has a strongly transitive edge partition, finding all cliques is not a hard task. First results of finding higher connected components conclude the report.

Kurzfassung

Knuth's words.dat ist eine umfangreiche Sammlung von Wörtern der englische Sprache, die 5 Buchstabe lang sind. Die Sammlung wird mit einer ungerichteten Graphenstruktur versehen. Für diesen Graphen wird eine vollständige Biblockzerlegung angegeben und untersucht. Außerdem werden alle Cliquen gefunden. Da words.dat eine stark transitive Kantenpartition aufweist, ist das nicht allzu schwer. Erste Ergebnisse zum Auffinden höherer Zusammenhangskomponenten beschließen den Bericht.

up

Download

up

Remarks

None.
up


Last change: 2007/06/17 (Stiege)