Nolte, Andreas and Schrader, Rainer
(1999).
Coloring in Sublinear Time.
Working Paper.
|
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: | Preprints, Working Papers or Reports (Working Paper) | ||||||||||||
| Creators: |
|
||||||||||||
| 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 |