Using graph coloring in an algebraic compiler
type: Item
instance of: scholarly article
title: Using graph coloring in an algebraic compiler
zbMATH Open document ID: 0865.68028
author: Teodor Rus
author: Sriram Pemmaraju
published in: Acta Informatica
publication date: 1996-09-25T00:00:00Z
review text: An algebraic compiler allows incremental development of the source program and builds its target image by composing the target images of the program components. In this paper we describe a general structure of an algebraic compiler focusing on compositional code generation. We show that the mathematical model for register management by an algebraic compiler is a graph coloring problem in which an optimally colored graph is obtained by composing optimally colored subgraphs. More precisely, we define the clique-composition of graphs \(G_1\) and \(G_2\) as the graph obtained by joining all the vertices in a clique in \(G_1\) with all the vertices in a clique in \(G_2\). We present a linear-time algorithm that takes as input optimally colored graphs \(G_1\) and \(G_2\) and constructs an optimal coloring of any clique-composition of \(G_1\) and \(G_2\). Motivated by the operation of clique-composition, we define the class of clique-composable graphs as those graphs that can be iteratively built from single vertices using the clique-composition operation. We show that the class of clique-composable graphs coincides with the well-known class of chordal graphs.
Mathematics Subject Classification ID: 68N20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 918715
zbMATH Keywords: algebraic compiler
zbMATH Keywords: graph coloring
zbMATH Keywords: optimally colored subgraphs
zbMATH Keywords: clique-composable graphs
MaRDI profile type: Publication
full work available at URL: s002360050079
OpenAlex ID: W2008487560
Wikidata QID: Q121875131
DOI: 10.1007/S002360050079
description: scientific article; zbMATH DE number 918715