Graph coloring in J: an introduction

ABSTRACT

Fundamentals of graph coloring are introduced, and four basic alternative algorithms for coloring undirected graphs are described in J, along with programs for generating, adjacency matrices and testing them. Results are compared, and suggestions for future development are offered.

REFERENCES

• 1: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 2: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 3: Olivier Coudert, Exact coloring of real-life graphs is easy, Proceedings of the 34th annual conference on Design automation, p.121-126, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266047]
• 4: David S. Johnson , Cecilia R. Aragon , Lyle A. McGeoch , Catherine Schevon, Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning, Operations Research, v.39 n.3, p.378-406, May-June 1991 [doi>10.1287/opre.39.3.378]
• 5: Leighton, F. T. "A Graph Coloring Algorithm for Large Scheduling Problems". Journal of Research for National Bureau of Standards. 84 (1979), 489-506.
• 6: Moll, Robert. University of Massachusetts Amherst Department of Computer Science (personal communication) December, 2000.
• 7: Steven R. Vegdahl, Using node merging to enhance graph coloring, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.150-154, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: J

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Languages