Coloring in Sublinear Time

Nolte, Andreas and Schrader, Rainer (1997) 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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Proceedings article
Citations: 6 (Google Scholar) |
Uncontrolled Keywords:
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
Related URLs:
Deposit Information:
ZAIK Number: zaik1999-352a
Depositing User: Rainer Schrader
Date Deposited: 02 Apr 2001 00:00
Last Modified: 17 Oct 2011 13:27