Improved edge-coloring with three colors |
| |
Authors: | ukasz Kowalik |
| |
Affiliation: | aInstitute of Informatics, University of Warsaw, Banacha 2, 02-097, Warsaw, Poland;bMax-Planck-Institute für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany |
| |
Abstract: | We show an O(1.344n)=O(20.427n) algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous O(2n/2) algorithm of Beigel and Eppstein R. Beigel, D. Eppstein, 3-coloring in time O(1.3289n), J. Algorithms 54 (2) (2005) 168–204.]. We apply a very natural approach of generating inclusion–maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique. |
| |
Keywords: | Edge-coloring Exponential-time Algorithm Measure and conquer |
本文献已被 ScienceDirect 等数据库收录! |
|