Full text
![[img]](http://oa.upm.es/style/images/fileicons/application_pdf.png)
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (925kB) |
A new DSATUR-based algorithm for exact vertex coloring
Citation
San Segundo Carrillo, Pablo (2011). A new DSATUR-based algorithm for exact vertex coloring. "Computers and Operations Research", v. 39 (n. 7); pp. 1-10. ISSN 0305-0548. https://doi.org/10.1016/j.cor.2011.10.008.
Description
| Title: | A new DSATUR-based algorithm for exact vertex coloring |
|---|---|
| Author/s: |
|
| Item Type: | Article |
| Título de Revista/Publicación: | Computers and Operations Research |
| Date: | 2011 |
| ISSN: | 0305-0548 |
| Volume: | 39 |
| Subjects: | |
| Freetext Keywords: | Color; Graph; Exact; DSATUR |
| Faculty: | E.U.I.T. Industrial (UPM) |
| Department: | Electrónica, Automática e Informática Industrial [hasta 2014] |
| Creative Commons Licenses: | Recognition - No derivative works - Non commercial |
Abstract
This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.
More information
| Item ID: | 11802 |
|---|---|
| DC Identifier: | https://oa.upm.es/11802/ |
| OAI Identifier: | oai:oa.upm.es:11802 |
| DOI: | 10.1016/j.cor.2011.10.008 |
| Official URL: | http://www.sciencedirect.com/science/article/pii/S0305054811002966 |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 06 Nov 2012 12:38 |
| Last Modified: | 22 Sep 2014 10:51 |
