Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme 		Universität Oldenburg   

Publications: Details

Document Description

Author: Guido Merker
Title: Hamiltonsche Graphen
Kind of Publication: Diplomarbeit
Supervisor: Prof. Stiege
Date: May, 2000
Institution: Universität Hildesheim, Institut für Betriebssysteme und Rechnerverbund
Pages, Language 134, German
Keywords: Hamiltonian graph
CR Classification: G.2.2 [Graph Theory]: Path and circuit problems; graph algorithms
General Terms (ACM): Theory, algorithms
up

Abstract

In a first part, this thesis collects sufficient or necessary conditions for the existence of a Hamiltonian circuit in a graph as presented in the textbook literature. Simple graphs, digraphs, and several classes of special graphs are considered.The result are presented in a uniform manner, classified and commented on. The second part contains newer results (from journal articles, new textbooks, the internet, and other sources). The third part is dedicated to procedures and algorithms for NP-complete problems, especially in Hamiltonian Graphs.

Kurzfassung

Im ersten Teil der Arbeit werden notwendige oder hinreichende Bedingungen für die Existenz eines Hamiltonkreises in einem Graphen, wie sie in der Lehrbuchliteratur zu finden sind, aufgeführt. Es werden schlichte Graphen, Digraphen und verschiedene spezielle Graphklassen berücksichtigt. Die Ergebniss werden einheitlich dargestellt, klassifiziert und kommentiert. Der zweite Teil entält neuere Resultate (aus Zeitschriften, neuen Textbüchern, dem Internet und anderen Quellen). Der dritte Teil ist Algorithmen zur Lösung NP-vollständiger Probleme, speziell in Hamiltonschen Graphen, gewidmet.

up

Download full text

up

Remarks

None


Last change: Sep. 30 2002 Stiege