Coloring in Sublinear Time
Nolte, Andreas and Schrader, Rainer
Coloring in Sublinear Time.
Published In: Algorithms - ESA '97 : 5th annual European symposium, Graz, Austria, September 15 - 17, 1997 ; proceedings, Lecture notes in computer science. 1284 Springer 1997, pp. 388-401.
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 proof for the excellent experimental performance results of Simulated Annealing known from the literature when applied to graph coloring problems.
|Item Type:||Proceedings article|
|Citations:||6 (Google Scholar) ||
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader|
|Depositing User:||Rainer Schrader|
|Date Deposited:||02 Apr 2001 00:00|
|Last Modified:||17 Oct 2011 13:27|