An experimental analysis of vertex coloring algorithms on sparse random graphs

Patrick Healy; Andrew Ju

doi:10.1007/978-3-319-04126-1_15

An experimental analysis of vertex coloring algorithms on sparse random graphs

Patrick Healy, Andrew Ju

Department of Computer Science & Information Systems

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The DSATUR algorithm for vertex coloring is popular both in its heuristic and exact (branch-and-bound) forms. Common to the known public implementations of the exact algorithm is the use of adjacency matrices to store the adjacency relations; this influences the algorithm’s implementation and its running time. In this paper we investigate the benefits of the introduction of supporting data structures to improve its running time: in addition to replacing the adjacency matrix by adjacency lists, thus shifting the focus from vertices to edges, we also introduce a priority queue data structure to assist in vertex selection. Our goal is to explore under which circumstances additional supporting data structures can speed up (exact) DSATUR.

Original language	English
Title of host publication	Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings
Editors	Prosenjit Gupta, Christos Zaroliagis
Publisher	Springer Verlag
Pages	174-186
Number of pages	13
ISBN (Electronic)	9783319041254
DOIs	https://doi.org/10.1007/978-3-319-04126-1_15
Publication status	Published - 2014
Event	1st International Conference on Applied Algorithms, ICAA 2014 - Kolkata, India Duration: 13 Jan 2014 → 15 Jan 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8321
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Conference on Applied Algorithms, ICAA 2014
Country/Territory	India
City	Kolkata
Period	13/01/14 → 15/01/14

Access to Document

10.1007/978-3-319-04126-1_15

Cite this

Healy, P., & Ju, A. (2014). An experimental analysis of vertex coloring algorithms on sparse random graphs. In P. Gupta, & C. Zaroliagis (Eds.), Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings (pp. 174-186). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8321). Springer Verlag. https://doi.org/10.1007/978-3-319-04126-1_15

Healy, Patrick ; Ju, Andrew. / An experimental analysis of vertex coloring algorithms on sparse random graphs. Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings. editor / Prosenjit Gupta ; Christos Zaroliagis. Springer Verlag, 2014. pp. 174-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2e2651d4e1854e458830bb55d1d08599,

title = "An experimental analysis of vertex coloring algorithms on sparse random graphs",

abstract = "The DSATUR algorithm for vertex coloring is popular both in its heuristic and exact (branch-and-bound) forms. Common to the known public implementations of the exact algorithm is the use of adjacency matrices to store the adjacency relations; this influences the algorithm{\textquoteright}s implementation and its running time. In this paper we investigate the benefits of the introduction of supporting data structures to improve its running time: in addition to replacing the adjacency matrix by adjacency lists, thus shifting the focus from vertices to edges, we also introduce a priority queue data structure to assist in vertex selection. Our goal is to explore under which circumstances additional supporting data structures can speed up (exact) DSATUR.",

author = "Patrick Healy and Andrew Ju",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 1st International Conference on Applied Algorithms, ICAA 2014 ; Conference date: 13-01-2014 Through 15-01-2014",

year = "2014",

doi = "10.1007/978-3-319-04126-1_15",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "174--186",

editor = "Prosenjit Gupta and Christos Zaroliagis",

booktitle = "Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings",

}

Healy, P & Ju, A 2014, An experimental analysis of vertex coloring algorithms on sparse random graphs. in P Gupta & C Zaroliagis (eds), Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8321, Springer Verlag, pp. 174-186, 1st International Conference on Applied Algorithms, ICAA 2014, Kolkata, India, 13/01/14. https://doi.org/10.1007/978-3-319-04126-1_15

An experimental analysis of vertex coloring algorithms on sparse random graphs. / Healy, Patrick; Ju, Andrew.
Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings. ed. / Prosenjit Gupta; Christos Zaroliagis. Springer Verlag, 2014. p. 174-186 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8321).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An experimental analysis of vertex coloring algorithms on sparse random graphs

AU - Healy, Patrick

AU - Ju, Andrew

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - The DSATUR algorithm for vertex coloring is popular both in its heuristic and exact (branch-and-bound) forms. Common to the known public implementations of the exact algorithm is the use of adjacency matrices to store the adjacency relations; this influences the algorithm’s implementation and its running time. In this paper we investigate the benefits of the introduction of supporting data structures to improve its running time: in addition to replacing the adjacency matrix by adjacency lists, thus shifting the focus from vertices to edges, we also introduce a priority queue data structure to assist in vertex selection. Our goal is to explore under which circumstances additional supporting data structures can speed up (exact) DSATUR.

AB - The DSATUR algorithm for vertex coloring is popular both in its heuristic and exact (branch-and-bound) forms. Common to the known public implementations of the exact algorithm is the use of adjacency matrices to store the adjacency relations; this influences the algorithm’s implementation and its running time. In this paper we investigate the benefits of the introduction of supporting data structures to improve its running time: in addition to replacing the adjacency matrix by adjacency lists, thus shifting the focus from vertices to edges, we also introduce a priority queue data structure to assist in vertex selection. Our goal is to explore under which circumstances additional supporting data structures can speed up (exact) DSATUR.

UR - http://www.scopus.com/inward/record.url?scp=84927605000&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-04126-1_15

DO - 10.1007/978-3-319-04126-1_15

M3 - Conference contribution

AN - SCOPUS:84927605000

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 174

EP - 186

BT - Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings

A2 - Gupta, Prosenjit

A2 - Zaroliagis, Christos

PB - Springer Verlag

T2 - 1st International Conference on Applied Algorithms, ICAA 2014

Y2 - 13 January 2014 through 15 January 2014

ER -

Healy P, Ju A. An experimental analysis of vertex coloring algorithms on sparse random graphs. In Gupta P, Zaroliagis C, editors, Applied Algorithms - 1st International Conference, ICAA 2014, Proceedings. Springer Verlag. 2014. p. 174-186. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-04126-1_15

An experimental analysis of vertex coloring algorithms on sparse random graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this