REAL

Determining the expected runtime of an exact graph coloring algorithm

Mann, Zoltán Ádám and Szajkó, Anikó (2011) Determining the expected runtime of an exact graph coloring algorithm. In: Proceedings of the 2010 Mini-Conference on Applied Theoretical Computer Science. University of Primorska Press, pp. 75-83. ISBN 978-961-6832-10-6

[img]
Preview
Text
Mann_Szajko_MATCOS_2011.pdf - Published Version

Download (298kB) | Preview

Abstract

Exact algorithms for graph coloring tend to have high vari- ance in their runtime, posing a signi�cant obstacle to their practical application. The problem could be mitigated by appropriate prediction of the runtime. For this purpose, we devise an algorithm to efficiently compute the expected run-time of an exact graph coloring algorithm as a function of the parameters of the problem instance: the graph's size, edge density, and the number of available colors. Specifically, we investigate the complexity of a typical backtracking algorithm for coloring random graphs with k colors. Using the expected size of the search tree as the measure of complexity, we devise a polynomial-time algorithm for predicting algorithm complexity depending on the parameters of the problem instance. Our method also delivers the expected number of solutions (i.e., number of valid colorings) of the given problem instance, which can help us decide whether the given problem instance is likely to be feasible or not. Based on our algorithm, we also show in accordance with previous results that increasing the number of vertices of the graph does not increase the complexity beyond some com- plexity limit. However, this complexity limit grows rapidly when the number of colors increases.

Item Type: Book Section
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr. Zoltán Ádám Mann
Date Deposited: 22 Sep 2014 20:52
Last Modified: 03 Apr 2023 08:16
URI: http://real.mtak.hu/id/eprint/16014

Actions (login required)

Edit Item Edit Item