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.

Descripción

Título: A new DSATUR-based algorithm for exact vertex coloring
Autor/es:
  • San Segundo Carrillo, Pablo
Tipo de Documento: Artículo
Título de Revista/Publicación: Computers and Operations Research
Fecha: 2011
Volumen: 39
Materias:
Palabras Clave Informales: Color; Graph; Exact; DSATUR
Escuela: E.U.I.T. Industrial (UPM) [antigua denominación]
Departamento: Electrónica, Automática e Informática Industrial [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (925kB)

Resumen

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.

Más información

ID de Registro: 11802
Identificador DC: http://oa.upm.es/11802/
Identificador OAI: oai:oa.upm.es:11802
Identificador DOI: 10.1016/j.cor.2011.10.008
URL Oficial: http://www.sciencedirect.com/science/article/pii/S0305054811002966
Depositado por: Memoria Investigacion
Depositado el: 06 Nov 2012 12:38
Ultima Modificación: 22 Sep 2014 10:51
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM