A new DSATUR-based algorithm for exact vertex coloring

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:
  • San Segundo Carrillo, Pablo
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

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (925kB)

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: http://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
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM