-
@TechReport{Bruynooghe85,
author = "M. Bruynooghe",
title = "{Graph Coloring and Constraint Satisfaction}",
institution = "Katholieke Universiteit Leuven",
number = "CW 44",
year = "1985",
}
@Article{Kubale85,
author = "M. Kubale and D. Jackowski",
title = "{A Generalized Implicit Enumeration Algorithm for
Graph Coloring}",
journal = "CACM",
volume = "28",
number = "4",
pages = "412--418",
year = "1985",
}
-
@Article{Coleman:1983:ESJ,
author = "T. F. Coleman and J. J. Mor\'e",
journal = j-siam-j-num-ana,
pages = "187--209",
title = "Estimation of sparse {J}acobian matrices and graph
coloring problems",
volume = "20",
year = "1983",
bibsource = "ftp://ftp.math.utah.edu/pub/bibnet/authors/m/more-jorge.bib",
}
@Article{Coleman:1984:ESH,
author = "T. F. Coleman and J. J. Mor\'e",
journal = j-math-prog,
pages = "243--270",
title = "Estimation of sparse {H}essian matrices and graph
coloring problems",
volume = "28",
year = "1984",
bibsource = "ftp://ftp.math.utah.edu/pub/bibnet/authors/m/more-jorge.bib",
}
-
@InProceedings
{Chaitin:acm:cc:1982,
author = "G. J. Chaitin",
title = "Register Allocation and Spilling via Graph Coloring",
crossref = "acm:cc:1982",
pages = "98--105",
refs = "6",
checked = "19940216",
source = "dept. library",
keywords = "SETL, source",
abstract = "In a previous paper we reported the successful use of
graph coloring techniques for doing global register
allocation in an experimental PL/1 optimizing compiler.
When the compiler cannot color the register conflict
graph with a number of colors equal to the number of
available machine registers, it must add code to spill
and reload registers to and from storage. Previously
the compiler produces spill code whose quality
sometimes left much to be desired, and the ad hoc
techniques used took considerable amounts of compile
time. We have now discovered how to extend te graph
coloring approach so that it naturally solves the
spilling problem. Spill decisions are now made on the
basis of the register conflict graph and cost estimates
of the value of keeping the result of a computation in
a register rather than in storage. This new approach
produces better object code and takes much less compile
time.",
reffrom = Auslander:Hopkins:acm:cc:1982,
reffrom = Chow:Henessy:acm:cc:1984,
}
-
@Article{briggs:94b,
author = "Preston Briggs and Keith D. Cooper and Linda Torczon",
title = "Improvements to Graph Coloring Register Allocation",
pages = "428--455",
journal = toplas,
year = "1994",
month = may,
volume = "16",
number = "3",
}
-
@Article{chaitin:82,
title = "Register Allocation and Spilling via Graph Coloring",
author = "Gregory J. Chaitin",
journal = sigplan,
year = "1982",
month = jun,
volume = "17",
number = "6",
note = pldi82,
pages = "98--105",
}
@Article{nickerson:90,
title = "Graph Coloring Register Allocation for Processors with
Multi-Register Operands",
author = "Brian R. Nickerson",
journal = sigplan,
year = "1990",
month = jun,
volume = "25",
number = "6",
note = pldi90,
pages = "40--52",
}
@Article{koblenz:91,
title = "Register Allocation via Hierarchical Graph Coloring",
author = "David Callahan and Brian Koblenz",
journal = sigplan,
year = "1991",
month = jun,
pages = "192--203",
note = pldi91,
number = "6",
volume = "26",
}
-
@Article{berger:90,
author = "B. Berger and J. Rompel",
title = "A better performance guarantee for approximate graph
coloring",
journal = "Algorithmica",
volume = "5",
number = "4",
pages = "459--466",
year = "1990",
}
@TechReport{briggs:92a,
author = "Preston Briggs",
title = "Register allocation via graph coloring",
institution = Rice,
type = "PhD Thesis",
number = "Rice COMP TR92-183",
year = "1992",
}
@InProceedings{callahan:91b,
author = "D. Callahan and B. Koblenz",
title = "Register allocation via hierarchical graph coloring",
booktitle = pldi91,
journal = sigplan,
volume = "26",
number = "6",
pages = "192--203",
address = "Toronto, Ontario, Canada",
month = June,
year = "1991",
}
@InProceedings{chaitin:82,
author = "Gregory J. Chaitin",
title = "Register allocation and spilling via graph coloring",
booktitle = cc82,
journal = sigplan,
volume = "17",
number = "6",
pages = "201--207",
month = June,
year = "1982",
}
@Article{garey:76,
author = "M. R. Garey and D. S. Johnson",
title = "The complexity of near-optimal graph coloring",
journal = jacm,
volume = "4",
pages = "397--411",
year = "1976",
}
@InProceedings{nickerson:90,
author = "B. R. Nickerson",
title = "Graph coloring register allocation for processors with
multi-register operands",
booktitle = pldi90,
journal = sigplan,
volume = "25",
number = "6",
pages = "40--52",
address = "White Plains, NY",
month = June,
year = "1990",
}
-
@InProceedings{CHAITIN82,
key = "Chaitin",
author = "G. J. Chaitin",
title = "Register Allocation and Spilling via Graph Coloring",
booktitle = "Proceedings of the SIGPlan '82 Symposium on Compiler
Construction",
address = "Boston, MA",
month = jun,
year = "1982",
pages = "98--105",
bibdate = "Tue Jan 10 09:54:16 1984",
}
@Article{DENCKER84,
key = "Dencker et al.",
author = "P. Dencker and K. Durre and J. Heuft",
title = "Optimization of Parser Tables for Portable Compilers",
journal = "toplas",
volume = "6",
number = "4",
month = oct,
year = "1984",
pages = "546--572",
keywords = "Graph coloring; sparse matrices; table compression",
abstract = "Six methods for parser table compression are compared.
The investigations are focused on four methods that
allow the access of table entries with a constant
number of index operations. The advantage of these
methods is that the access to the compressed tables can
be programmed efficienctly in portable high-level
languages like Pascal or FORTRAN. The results are
related to two simple methods based on list searching.
Experimental results on eleven different grammers show
that, on the average, a method based on graph coloring
turns our best.",
bibdate = "Thu Feb 7 11:53:52 1985",
}
@InProceedings{LARUS86,
key = "Larus \& Hilfinger",
author = "J. R. Larus and P. N. Hilfinger",
title = "Register Allocation in the {SPUR} Lisp Compiler",
booktitle = "SIGPlan '86 Symposium on Compiler Construction",
organization = "acm",
publisher = "SIGPlan",
address = "Palo Alto, CA",
month = jun,
year = "1986",
pages = "255--263",
abstract = "Register allocation is an important component of most
compilers, particularly those for RISC machines. The
SPUR Lisp compiler uses a sophisticated, graph-coloring
algorithm developed by Fredrick Chow. This paper
describes the algorithm and evaluates its performance
on several large programs. The allocator successfully
assigned most temporaries and local variables to
registers in a wide variety of functions. Its execution
cost is moderate.",
bibdate = "Thu Feb 26 13:19:23 1987",
owner = "manning",
}
@InProceedings{WALL86,
key = "Wall",
author = "D. W. Wall",
title = "Global Register Allocation at Link Time",
booktitle = "SIGPlan '86 Symposium on Compiler Construction",
organization = "acm",
publisher = "SIGPlan",
address = "Palo Alto, CA",
month = jun,
year = "1986",
pages = "264--275",
abstract = "In previous work in global register allocation, the
compiler colors a conflict graph constructed from
liveness dataflow information, in order to allocate the
same register to many variables that are not
simultaneously live. If two procedures are in
separately compiled modules, however, the compiler must
do this allocation separately for each procedure. As a
result, the two procedures might use different
registers for the same global, or the same register for
different locals. We can remove these problems if we
delay the register allocation until link time. Our
compiler produces object modules that can be linked and
run without global register allocation, but includes
with each object module a body of information
describing how the module uses variables and
procedures. A link-time register allocator then decides
which variables are used most frequently, selects
registers for them, and rewrites the code to reflect
the decision that these variables reside in registers
rather than in memory. Construction of the call graph
allows us to use the same register for locals of
procedures that are not simultaneously active, giving
us most of the advantages of a full-scale coloring
without the expense. When we use our method of 52
registers, our benchmarks speed up by 10 to 25 percent.
Even with only 8 registers, the speedup can be nearly
that large if we use previously collected profile
information to guide the allocation. We cannot do much
better, because programs whose variables all fit in
registers rarely speed up by more than 30\%. Moreover,
profiling shows us that we usually remove 60\% to 90%
of the loads and stores of scalar variables that the
program performs during its execution, and often much
more.",
bibdate = "Thu Feb 26 13:31:29 1987",
owner = "manning",
}
-
@InProceedings{KESS:PAU:RAU:1991,
author = "Christoph W. Kessler and W. J. Paul and T. Rauber",
title = "{\em``Register Allocation and Code Optimization for
Vector Basic Blocks on Vector Processors''}",
booktitle = "{``Code Generation --- Concepts, Tools, Techniques'',
Proceedings of the International Workshop on Code
Generation, Dagstuhl, Germany, 20-24 May 1991}",
editor = "Robert Giegerich and Susan L. Graham",
series = "Workshops in Computing",
year = "1991",
pages = "73--91",
publisher = "Springer-Verlag",
note = "ISBN 3-540-19757-5 and 3-387-19757-5",
abstract = "We present a randomized heuristic algorithm to
generate continuous evaluations for expression DAGs
with nearly minimal register need. The heuristic may be
used to reorder the statements in a basic block before
applying a global register allocation scheme like graph
coloring. Experiments have shown that the new heuristic
produces results about 30\% better on the average than
without reordering. Basic blocks of vector instructions
lead to vector DAGs. For the special class of
quasiscalar DAGS, the problem can be reduced to the
scalar case handled above provided that some machine
constraints such as buffer size and pipeline depth are
taken into consideration. Theorectical considerations
show that there exists an interesting tradeoff-effect
between strip miningan vector register spilling.
Therefore we give an algorithm which computes the best
ratio of spill rate to strip length with respect to the
run time on the target vector processor which is given
by some architecture parameters. This algorithm is
suited for vector processors containing a buffer
(register file) which may be partitioned arbitrarily by
the user.",
}
-
@Article{Chams1987,
author = "M. Chams and A. Hertz and D. de Werra",
title = "Some Experiments with simulated annealing for coloring
graphs",
journal = "European Journal of Operational Research, Vol. 32, :",
year = "1987",
pages = "260--266",
references = "0",
language = "English",
enum = "9452",
descriptors = "heuristics; simulation; manufacturing system;
production system; scheduling;",
date = "01/07/93",
annote = "(VBI-002210) simulator; Abstract: Methods of
thermodynamical simulation have been used for several
famous combinatorial optimization problems. For graph
coloring (i.e. partition of the node set into as few
independent sets as possible) we describe a method of
simulation. Such an approach is combined with other
techniques for graph coloring. Experiments on random
graphs show evidence that this combination gives better
results than anyone of the",
}
@Article{Hertz1987,
author = "A. Hertz and D. de Werra",
title = "Using Tabu Search Techniques for Graph Coloring",
journal = "Computing, Vol. 39, :",
year = "1987",
pages = "345--351",
references = "0",
language = "English",
enum = "10007",
descriptors = "graph marking algorithm;",
date = "01/07/93",
annote = "(VBI-002212) graph coloring; tabu search; simulated
annealing; Abstract: Tabu search techniques are used
for moving step by step towards the minimum value of a
function. A tabu list of forbidden movements is updated
during the iterations to avoid cycling and being
trapped in local minima. Such techniques are adapted to
graph coloring problems. We show that they provide
almost optimal coloring of graphs having up to 1000
nodes and their efficien",
}
-
@Article{Lofti1986,
author = "V. Lofti and S. Sarin",
title = "A Graph Coloring Algorithm for Large Scale Scheduling
Problems",
journal = "Comput. & Ops. Res., Vol. 13, :1, 27-32",
year = "1986",
references = "0",
language = "English",
enum = "10462",
descriptors = "graph marking algorithm; frequency distribution;",
date = "01/07/93",
annote = "(VBI-002764) Graph colouring;",
}
-
@InProceedings{SoklicZ91,
author = "M. E. Soklic and J. Zerovnik",
title = "{Distributed Simulation of Coloring Graph Vertices}",
booktitle = "Annual Simulation Symposium. Record of Proceedings",
year = "1991",
pages = "118--122",
anmerkung = "Abstract",
bibinfo = "\bib{SoklicZ91}{\anwendung}{\kopie}{\transputer,
\hierarchisch}",
}
-
@Article{HLM+90,
author = "S. H. Hosseini and B. Litow and M. Malkawi and J.
McPherson and K. Vairavan",
title = "Analysis of a Graph Coloring Based Distributed Load
Balancing Algorithm",
journal = "Journal of Parallel and Distributed Computng",
year = "1990",
pages = "160--166",
month = oct,
}
-
@InProceedings{lieberman78a,
author = "H. Lieberman",
title = "How to color in a coloring book",
pages = "111--116",
journal = "Computer Graphics (SIGGRAPH '78 Proceedings)",
volume = "12",
number = "3",
year = "1978",
month = aug,
conference = "held in Atlanta, Georgia; 23 -- 25 August 1978",
keywords = "filling algorithm",
}
-
@Article{welstead89a,
author = "Stephen T. Welstead and Thomas L. Cromer",
title = "Coloring periodicities of two-dimensional mappings",
pages = "539--543",
journal = "Computers and Graphics",
volume = "13",
number = "4",
year = "1989",
keywords = "",
annote = "",
}
-
@Article{Rosenfeld89c,
author = "A. Rosenfeld",
title = "Arc Colorings, Partial Path Groups, and Parallel Graph
Contractions",
volume = "7",
pages = "335--354",
institution = "U Md",
journal = JPDC,
keywords = "INFORMATION PROCESSING, TIME",
year = "1989",
}
-
@Article{welstead-1989-coloring,
author = "Stephen T. Welstead and Thomas L. Cromer",
title = "Coloring periodicities of two-dimensional mappings",
pages = "539--543",
journal = "Computers and Graphics",
volume = "13",
number = "4",
year = "1989",
}
-
@Article{tucker-1984-algorithm,
author = "A. Tucker and D. Wilson",
title = "An {$O(N^{2})$} algorithm for coloring perfect planar
graphs",
journal = "J. Algorithms",
volume = "5",
year = "1984",
pages = "60--68",
oldlabel = "geom-969",
}
-
@InProceedings{lieberman-1978-how,
author = "H. Lieberman",
title = "How to color in a coloring book",
pages = "111--116",
journal = "Computer Graphics (SIGGRAPH '78 Proceedings)",
volume = "12",
number = "3",
year = "1978",
month = aug,
conference = "held in Atlanta, Georgia; 23 -- 25 August 1978",
keywords = "filling algorithm",
}
-
@Book{IB-73149,
editor = "C. Read",
title = "Graph Theory and Computing",
publisher = "Academic Press",
address = "New York",
year = "1972",
descriptor = "Baum, Faerbbarkeit, Matching, Planaritaet,
Ueberdeckung, Graph, Graphentheorie",
annote = "Ueberschriften einiger Artikel: Alternating chain
methods: A survey The average height of plated plane
trees How to number a graph The production of graphs by
computer A graph theoretic programming language Graph
coloring algorithms Non-Hamiltonian planar maps",
}
-
@Proceedings{IB-B76427,
editor = "IEEE and Institute of Electrical and Electronics
Engineers",
title = "16th Annual Symposium on Foundations of Computer
Science (Formerly Called the Annual Symposium on
Swithing and Automata Theory), October 13-15, 1975, The
University of California, Berkeley",
address = "Long Beach",
year = "1975",
descriptor = "Entscheidungsproblem, Kontextfreie Sprache, Parser,
Sortieralgorithmus, Strukturiertes Programmieren,
Graphentheorie, Informationstheorie, Sprache,
Komplexitaet, Parallelverarbeitung",
annote = "Session I: - The effect of the field of constants on
the number of multiplications - The exact time required
to perform generalized addition - Polinomials with 0-1
coefficients that are hard to evaluate - Fast parallel
matrix inversion algorithms - Parallel computations in
graph theory - Synchronization and computing
capabilities of linear asynchronous structures Sesion
II: - Flow of control in the proof theory of structured
programming - Bases for chain-complete posets - Correct
computation rules for recursive languages - On time
versus space and related problems - A note on tape
bounds for SLA language processing Session III: -
Minimean optimality in sorting algorithms - Preserving
order in a forest in less than logarithmic time - On
the complexity of comparison problems using linear
functions - Evaluating relational expressions with
dense and sparse arguments - On the decision tree
complexity of the shortest path problems - An O(n hoch
2.5) algorithm for maximum matching in general graphs
Session IV: - Information theory and the complexity of
switching networks - The effect of basis on size of
boolean expressions - Economy of description by
parsers, Dpda's, and Pda's - An improvement on
Valiant's decision procedure for equivalence of
deterministic finite-turn pushdown automata - A
grammatical characterization of exponential-time
languages - Decidability of equivalence, containment,
intersection, and separability of context-free
languages Session V: - Closest-point problems - An
optimal bound for two dimensional bin packing -
Computational complexity of decision procedures for
polynomials - An application of graph coloring to
printed circuit testing - On the complexity of
timetable and multi-commodity flow problems",
}
-
@Book{IB-A80124,
editor = "L. W. Beineke and R. J. Wilson",
title = "Selected Topics in Graph Theory",
publisher = "Academic Press",
address = "London",
year = "1978",
ISBN = "0-12-086250-6",
descriptor = "Digraph, Eigenwert von Graphen, Hamilton-Graph,
Topologische Graphentheorie, Vierfarbenproblem,
Graphentheorie",
annote = "1. Introduction 2. Topological graph theory 3. The
proof of the Heawood conjecture 4. The Appel-Haken
proof of the four-color theorem 5. Edge-colorings of
graphs 6. Hamiltonian graphs 7. Tournaments 8. The
reconstruction problem 9. Minimax theorems in graph
theorem 10. Line graphs and line digraphs 11.
Eigenvalues of graphs 12. Strongly regular graphs 13.
Ramsey graph theory 14. The enumeration of graphs 15.
Some applications of computers in graph theory Index of
definitions",
}
-
@InProceedings{Chow:1984:RAP,
author = "F. Chow and J. Hennessy",
title = "Register allocation by priority-based coloring",
crossref = "VanDeusen:1984:CCP",
pages = "222--232",
year = "1984",
acknowledgement = ack-nhfb,
bibdate = "Sat Aug 13 17:16:20 MDT 1994",
keywords = "languages; measurement; algorithms",
subject = "E Data, DATA STRUCTURES \\ G.2.2 Mathematics of
Computing, DISCRETE MATHEMATICS, Graph Theory, Graph
algorithms",
}
@Article{Briggs:1989:CHR,
author = "P. Briggs and K. D. Cooper and K. Kennedy and L.
Torczon",
title = "Coloring heuristics for register allocation",
journal = j-SIGPLAN,
volume = "24",
number = "7",
pages = "275--284",
month = jul,
year = "1989",
ISSN = "0362-1340",
acknowledgement = ack-nhfb,
bibdate = "Sat Aug 13 17:16:20 MDT 1994",
keywords = "algorithms; languages; performance; theory",
subject = "D.3.4 Software, PROGRAMMING LANGUAGES, Processors,
Optimization \\ D.3.2 Software, PROGRAMMING LANGUAGES,
Language Classifications, FORTRAN \\ G.2.2 Mathematics
of Computing, DISCRETE MATHEMATICS, Graph Theory, Graph
algorithms \\ F.2.2 Theory of Computation, ANALYSIS OF
ALGORITHMS AND PROBLEM COMPLEXITY, Nonnumerical
Algorithms and Problems, Computations on discrete
structures",
}
-
@Article{Hopcroft:1983:HCG,
author = "J. E. Hopcroft and M. S. Krishnamoorthy",
title = "On the harmonious coloring of graphs",
journal = j-SIAM-J-ALG-DISC-METH,
year = "1983",
volume = "4",
number = "3",
pages = "306--311",
month = sep,
note = "Work related to minimal perfect hash functions.",
acknowledgement = ack-nhfb,
bibdate = "Mon Jul 18 22:33:00 1994",
}
-
@Article{Rubinstein:1988:SCA,
author = "D. Rubinstein and J. Shallit and M. Szegedy",
title = "A subset coloring algorithm and its applications to
computer graphics",
journal = j-CACM,
volume = "31",
number = "10",
pages = "1228--1232",
month = oct,
year = "1988",
ISSN = "0001-0782",
acknowledgement = ack-nhfb,
bibdate = "Sun Aug 14 18:32:13 MDT 1994",
keywords = "algorithms; design; performance",
subject = "I.3.3 Computing Methodologies, COMPUTER GRAPHICS,
Picture/Image Generation, Display algorithms \\ I.3.7
Computing Methodologies, COMPUTER GRAPHICS,
Three-Dimensional Graphics and Realism, Color, shading,
shadowing, and texture \\ I.3.1 Computing
Methodologies, COMPUTER GRAPHICS, Hardware
architecture, Raster display devices",
}
-
@Article{ChrobakYung89,
key = "Chrobak \& Yung",
author = "Marek Chrobak and Moti Yung",
title = "Fast Algorithms for Edge-Coloring Planar Graphs",
journal = "Journal of Algorithms",
pages = "35--51",
volume = "10",
number = "1",
month = mar,
year = "1989",
location = "CMU E \& S Library",
}
@Article{Vishwanathan92,
key = "Vishwanathan",
author = "S. Vishwanathan",
title = "Randomized Online Graph Coloring",
journal = "Journal of Algorithms",
pages = "657--669",
volume = "13",
number = "4",
month = dec,
year = "1992",
location = "CMU Engineering \& Science Library",
}
-
@Article{RubinsteinShallitSzegedy88,
key = "Rubinstein et al.",
author = "David Rubinstein and Jeffrey Shallit and Mario
Szegedy",
title = "A Subset Coloring Algorithm and Its Applications to
Computer Graphics",
journal = "Communications of the ACM",
pages = "1228--1232",
volume = "31",
number = "10",
month = oct,
year = "1988",
location = "CMU E\&S Library: Association for Computing Machinery.
Communications",
}
-
@Article{Goldberg:1987:PGD,
author = "Andrew V. Goldberg and Serge A. Plotkin",
title = "Parallel {((Greek {D}){D}+1)}-coloring of
constant-degree graphs",
journal = j-INFO-PROC-LETT,
volume = "25",
number = "4",
pages = "241--245",
month = jun,
year = "1987",
ISSN = "0020-0190",
acknowledgement = ack-nhfb,
bibdate = "Wed Aug 24 13:27:07 1994",
keywords = "algorithms; theory; verification",
subject = "G.1.0 Mathematics of Computing, NUMERICAL ANALYSIS,
General, Parallel algorithms \\ G.2.2 Mathematics of
Computing, DISCRETE MATHEMATICS, Graph Theory, Graph
algorithms",
}
@Article{Naor:1987:FPC,
author = "Joseph Naor",
title = "A fast parallel coloring of planar graphs with five
colors",
journal = j-INFO-PROC-LETT,
volume = "25",
number = "1",
pages = "51--53",
month = apr,
year = "1987",
ISSN = "0020-0190",
acknowledgement = ack-nhfb,
bibdate = "Mon Aug 15 13:51:01 MDT 1994",
keywords = "theory; verification; algorithms",
subject = "G.1.0 Mathematics of Computing, NUMERICAL ANALYSIS,
General, Parallel algorithms \\ F.2.2 Theory of
Computation, ANALYSIS OF ALGORITHMS AND PROBLEM
COMPLEXITY, Nonnumerical Algorithms and Problems \\
G.2.2 Mathematics of Computing, DISCRETE MATHEMATICS,
Graph Theory, Graph algorithms",
}
@Article{Ho:1988:EPA,
author = "Chin-Wen Ho and Richard C. T. Lee",
title = "Efficient parallel algorithms for finding maximal
cliques, clique trees, and minimum coloring on chordal
graphs",
journal = j-INFO-PROC-LETT,
volume = "28",
number = "6",
pages = "301--309",
month = aug,
year = "1988",
ISSN = "0020-0190",
acknowledgement = ack-nhfb,
bibdate = "Mon Aug 15 13:51:01 MDT 1994",
keywords = "algorithms; theory; performance; verification",
review = "ACM CR 8909-0674 8909-0673",
subject = "G.2.2 Mathematics of Computing, DISCRETE MATHEMATICS,
Graph Theory, Graph algorithms \\ G.2.2 Mathematics of
Computing, DISCRETE MATHEMATICS, Graph Theory, Trees \\
F.1.2 Theory of Computation, COMPUTATION BY ABSTRACT
DEVICES, Modes of Computation, Parallelism \\ F.2.2
Theory of Computation, ANALYSIS OF ALGORITHMS AND
PROBLEM COMPLEXITY, Nonnumerical Algorithms and
Problems, Computations on discrete structures",
}
-
@Article{RuShSz88,
author = "D. Rubinstein and J. Shallit and M. Szegedy",
title = "A Subset Coloring Algorithm and Its Applications to
Computer Graphics",
journal = "Communications of the ACM, CACM",
volume = "31",
number = "10",
pages = "1228--1231",
publisher = "ACM Press , New York, NY , USA",
month = "[10]",
year = "1988",
}
@Article{Hsu88,
author = "W.-L. Hsu",
title = "The Coloring and Maximum Independent Set Problems on
Planar Perfect Graphs",
journal = "Journal of the ACM, JACM",
volume = "35",
number = "3",
pages = "535--563",
publisher = "ACM Press , New York, NY , USA",
month = "[7]",
year = "1988",
}
@Article{Rosenf89,
author = "A. Rosenfeld",
title = "Arc Colorings, Partial Path Groups, and Parallel Graph
Contractions",
journal = "Journal of Parallel and Distributed Computing",
volume = "7",
number = "2",
pages = "335--354",
publisher = "Academic Press , San Diego, New York, Boston, London,
Syndey, Tokyo, Toronto",
month = "[10]",
year = "1989",
}
@Article{HLMMV90,
author = "S. H. Hosseini and B. Litow and M. Malkawi and J.
McPherson and K. Vairavan",
title = "Analysis of a Graph Coloring Based Distributed Load
Balancing Algorithm",
journal = "Journal of Parallel and Distributed Computing",
volume = "10",
number = "2",
pages = "160--166",
publisher = "Academic Press , San Diego, New York, Boston, London,
Syndey, Tokyo, Toronto",
month = "[10]",
year = "1990",
}
@InProceedings{BhKrSi88,
author = "I. S. Bhandari and C. M. Krishna and D. P. Siewiorek",
title = "A Parallel Algorithm for Coloring Graphs",
booktitle = "Proceedings of the 8th International Conference on
Distributed Computing Systems (ICDCS)",
pages = "326--333",
publisher = "IEEE Computer Society , Washington, DC",
address = "San Jose, CA USA",
year = "1988",
}
@InProceedings{CalKob91,
author = "D. Callahan and B. Koblenz",
title = "Register Allocation via Hierarchical Graph Coloring",
booktitle = "Proceedings of the ACM SIGPLAN '91 Conference on
Programming Language Design and Implementation (PLDI)",
pages = "192--203",
address = "Toronto, ON CDN",
month = "[6]",
year = "1991",
note = "Published as SIGPLAN Notices, volume 26, number 6",
}
-
@Article{Olariu1,
author = "S. Olariu",
title = "An optimal greedy heuristic to color interval graphs",
journal = ipl,
volume = "37",
pages = "21--25",
year = "1991",
comment = "``We characterize interval graphs in terms of a
certain linear order on their vertex set. It turns out
that with this linear order, the well known greedy
heuristic -- always use the smallest available color --
yields an exact coloring algorithm for interval graphs.
In addition, the heuristic can be implemented to run in
linear time.''",
}
-
@Article{Chaitin:1,
author = "G. Chaitin",
title = "Register Allocation and Spilling Via Graph Coloring",
year = "1982",
journal = "Proc. SIGPLAN Symp. Compiler Construction",
keywords = "mips risc reduced restricted instruction set computer
architecture pipelining microcoding",
}
-
@Article{AMBLER83,
key = "Ambler \& Trawick",
author = "A. Ambler and R. Trawick",
title = "Chaitin's Graph Coloring Algorithm as a Method for
Assigning Positions to Diana Attributes",
journal = "sigplan",
volume = "18",
number = "2",
month = feb,
year = "1983",
pages = "37--38",
keywords = "Diana, attributed grammer",
abstract = "Diana, the widely used abstraction for Ada compilers'
intermediate representation for Ada programs, consists
of graphs of attributed nodes. A graph-coloring
algorithm allocates positions for attributes within
nodes of a graph, making a space and time-efficient
implementation.",
bibdate = "Tue Jan 10 09:39:51 1984",
}
Limit of 30 bibliographies exceeded...