Circular-arc graph coloring: On chords and circuits in the meeting graph |
| |
| Affiliation: | 1. Département de Mathématiques, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland;2. INRIA, Projet A3, Domaine de Voluceau, Rocquencourt, BP 105, F-78153 Le Chesnay Cedex, France;3. Institut für Computersprachen, Technische Universität Wien, Argentinierstraße 8, A-1040 Wien, Austria;4. Department of Computer Science, University of Manchester, Manchester M13 9PL, UK;1. Department of Pure and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa;2. Department of Mathematics, East Carolina University, Greenville, NC 27858, USA;3. School of Mathematics, University of the Witwatersrand, Johannesburg, South Africa;1. Lehrstuhl für Informatik I, Universität Würzburg, Germany;2. Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic;1. Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA;2. Institute for Mathematics, Arnimallee 6, D-14195, Freie Universität, Berlin, Germany |
| |
| Abstract: | ![]()
In compilers register allocation in loops is usually performed by coloring a corresponding circular-arc graph. Generally, the problem of finding the chromatic number of circular-arc graphs is known to be NP-complete. Thus, approximation algorithms should be considered. In this paper we propose heuristics based on decomposition of a so called meeting graph into a set of circuits. We explain the importance of the meeting graph for our solutions and prove properties of our decomposition of the graph into circuits. We derive inequalities relating the number of circuits in the decomposition to the size of the maximum stable set of chords, and present experimental results. Finally, we discuss the quality of our heuristics for circular-arc graph coloring. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
