Nolte, Andreas and Schrader, Rainer (1999). Coloring in Sublinear Time. Working Paper.

[thumbnail of zaik1999-352.pdf]
Preview
 PDF
zaik1999-352.pdf
Download (304kB) | Preview

Abstract

We will present an algorithm, based on SA-techniques and a sampling procedure, that colors a given random 3-colorable graph with high probability in sublinear time. This result is the first theoretical justification of many excellent experimental performance results of Simulated Annealing applied to graph coloring problems.

Item Type: Monograph (Working Paper)
Creators:
Creators
Email
ORCID
ORCID Put Code
Nolte, Andreas
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Schrader, Rainer
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
URN: urn:nbn:de:hbz:38-548368
Date: 1999
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54836

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item