**1**-
E.H.L. Aarts and J.H.M Korst.
*Simulated Annealing and Boltzmann Machines*. John Wiley & Sons, Chichester, U.K., 1989. **2**-
E.A. Akkoyunlu.
The enumeration of maximal cliques of large graphs.
*SIAM Journal on Computing*, 2(1):1-6, 1973. **3**-
K. Appel and W. Haken.
Every planar map is 4-colorable - 1: Discharging.
*Illinois Journal of Mathematics*, 21:421-490, 1977. **4**-
K. Appel and W. Haken.
Every planar map is 4-colorable - 2: Reducibility.
*Illinois Journal of Mathematics*, 21:491-567, 1977. **5**-
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy.
Proof verification and hardness of approximation problems.
In
*Proceedings 33rd IEEE Symposium on the Foundations of Computer Science*, pages 14-23, Los Angeles, CA, 1992. IEEE Computer Society. **6**-
S. Arora and S. Safra.
Probabilistic checking of proofs; a new characterization of np.
In
*Proceedings 33rd IEEE Symposium on Foundations of Computer Science*, pages 2-13, Los Angeles, CA, 1992. IEEE Computer Society. **7**-
Luitpold Babel.
Finding maximum cliques in arbitrary and in special graphs.
*Computing*, 46:321-341, 1991. **8**-
Egon Balas and H. Samuelsson.
A node covering algorithm.
*Naval Research Logistics Quarterly*, 24(2):213-233, 1977. **9**-
Egon Balas and Jue Xue.
Minimum weighted coloring of triangulated graphs, with application to
maximum weight vertex packing and clique finding in arbitrary graphs.
*SIAM Journal on Computing*, 20(2):209-221, 1991. **10**-
Egon Balas and Chang Sung Yu.
Finding a maximum clique in an arbitrary graph.
*SIAM Journal on Computing*, 15(4):1054-1068, 1986. **11**-
Jean-Pierre Barthélemy and Alain Guénoche.
*Trees and Proximity Representations*. John Wiley and Sons, New York, NY, 1991. **12**-
B. Berger and J. Rompel.
A better permance guarantee for approximate graph coloring.
*Algorithmica*, 5:459-466, 1990. **13**-
A. Blum.
An -approximation algorithm for 3-coloring
(and improved approximation algorithms for -coloring).
In
*Proceedings 21st ACM Symposium on Theory of Computing*, pages 535-542, New York, 1989. ACM. **14**-
A. Blum.
Some tools for approximate 3-coloring.
In
*Proceedings 31st IEEE Symposium on Foundations of Computer Science*, pages 554-562, Los Angeles, CA, 1990. IEEE Computer Society. **15**-
B. Bollobás.
The chromatic number of random graphs.
*Combinatorica*, 8:49-56, ??? **16**-
B. Bollobás and P. Erdös.
Cliques in random graphs.
*Mathematical Proceedings of the Cambride Philosophical Society*, 80:419-427, 1976. **17**-
B. Bollobas and A. Thomason.
Random graphs of small order.
*Annals of Discrete Math.*, 28:47-97, 1985. **18**-
D. Brélaz.
New methods to color vertices of a graph.
*Communications of the ACM*, 22:251-256, 1979. **19**-
P. Briggs, K. Cooper, K. Kennedy, and L. Torczon.
Coloring heuristics for register allocation.
In
*ASCM Conference on Program Language Design and Implementation*, pages 275-284, 1989. **20**-
Coen Bron and Joep Kerbosch.
Finding all cliques of an undirected graph.
*Communications of the ACM*, 16(9):575-577, 1973. **21**-
R. J. Brown.
Chromatic scheduling and the chromatic number problem.
*Management Science*, 19:451-463, 1972. **22**-
R. Carraghan and P. M. Pardalos.
An exact algorithm for the maximum clique problem.
*Operations Research Letters*, 9:375-382, 1990. **23**-
V. Cerny.
A thermodynamical approach to the traveling saleman problem: An
efficient simulation algorithm.
*Journal of Optimization Theory and Applications*, 45:41-51, 1985. **24**-
G.J. Chaitin.
Register allocation and spilling via graph coloring.
In
*Proceedings of the ACM SIGPLAN 82 Symposium on Compiler Construction*, pages 98-105, New York, NY, 1982. ACM. **25**-
G.J. Chaitin, M. Auslander, A.K. Chandra, J. Cocke, M.E. Hopkins, and
P. Markstein.
Register allocation via coloring.
*Coputer Languages*, 6:47-57, 1981. **26**-
M. Chams, A. Hertz, and D. De Werra.
Some experiments with simulated annealing for coloring graphs.
*European Journal of Operations Research*, 32:260-266, 1987. **27**-
Fred C. Chow and John L. Hennessy.
Register allocation by priority-based coloring.
In
*Proceedings of the ACM SIGPLAN 84 Symposium on Compiler Construction*, pages 222-232, New York, NY, 1984. ACM. **28**-
Fred C. Chow and John L. Hennessy.
The priority-based coloring approach to register allocation.
*ACM Transactions on Programming Languages and Systems*, 12(4):501-536, 1990. **29**-
N. Christofides.
An algorithm for the chromatic number of a graph.
*Computer Journal*, 14:38-39, 1971. **30**-
N. Christofides.
*Graph Theory: An Algorithmic Approach*. Academic Press, London., 1975. **31**-
N.E. Collins, R.W. Eglese, and B.L. Golden.
Simulated annealing: An annotated bibliography.
*American Journal of Mathematical and Management Sciences*, 8:205-307, 1988. **32**-
D. G. Corneil and B. Graham.
An algorithm for determining the chromatic number of a graph.
*SIAM Journal on Computing*, 2:311-218, 1973. **33**-
D. De Werra.
An introduction to timetabling.
*European Journal of Operations Research*, 19:151-162, 1985. **34**-
M. Dyer and A. Frieze.
The solution of some random np-hard problems in polynomial expected
time.
*Journal of Algorithms*, 10:451-489, 1989. **35**-
U. Feige, S. Goldwasser, L. Lovasz, S. Safra, , and M. Szegedy.
Approximating clique is almost NP-complete.
In
*Proceedings 32nd IEEE Symposium on Foundations of Computer Science*, pages 2-12, Los Angeles, CA, 1991. IEEE Computer Society. **36**-
T. A. Feo, M. G. C. Resende, and S. H. Smith.
Greedy randomized adaptive search procedure for maximum independent
set.
*Operations Research*, page (to appear), 1993. **37**-
M. Fürer and C. R. Subramanian.
Coloring random graphs.
In
*Proceedings 3rd Scandinavian Workshop on Algorithmic Theory*, Berlin, 1992. Springer Lecture Notes in Computer Science. **38**-
Andreas Gamst.
Some lower bounds for a class of frequency assignment problems.
*IEEE Transactions of Vehicular Echnology*, 35(1):8-14, 1986. **39**-
M. R. Garey, D. S. Johnson, and H. C. So.
An application of graph coloring to printed circuit testing.
*IEEE Trans. on Circuits and Systems*, CAS-23:591-599, 1976. **40**-
Michael R. Garey and David S. Johnson.
The complexity of near-optimal graph coloring.
*Journal of the Association for Computing Machinery*, 23:43-49, 1976. **41**-
Michael R. Garey and David S. Johnson.
*Computers and Instractability: A Guide to the Theory of NP-Completeness*. W.H Freeman, San Francisco, CA, 1979. **42**-
L. Gerhards and W. Lindenberg.
Clique detection for nondirected graphs: Two new algorithms.
*Computing*, 21:295-322, 1979. **43**-
Fred Glover.
Tabu search, part 1.
*ORSA Journal on Computing*, 1:190-206, 1989. **44**-
D. E. Goldberg.
*Genetic Algorithms in Search, Optimization & Machine Learning*. Addison-Wesley, Reading, MA, 1989. **45**-
M. Golumbic.
*Algorithmic Graph Theory and Perfect Graphs*. Acadmeic Press, New York, NY, 1980. **46**-
G.R. Grimmet and C.J.H. McDiarmid.
On colouring random graphs.
*Mathematical Proceedings of the Cambridge Philosophical Society*, 77:313-324, 1975. **47**-
M. M. Halldórsson.
A still better performance guarantee for approximate graph coloring.
Technical Report 91-35, DIMACS, New Brunswick, NJl, 1990.
**48**-
J. Hasselberg, P. M. Pardalos, and G. Vairaktarakis.
Test case generators and computational results for the maximum clique
problem.
Working paper, University of Florida, 1992.
**49**-
A. Hertz and D. De Werra.
Using tabu search techniques for graph coloring.
*Computing*, 39:345-351, 1987. **50**-
Mark Jerrum.
Large cliques elude the metropolis process.
*Random Structures and Algorithms*, 3(4):347-360, 1992. **51**-
David S. Johnson.
Approximation algorithms for combinatorial problems.
*Journal of Computer and System Sciences*, 9:256-278, 1974. **52**-
David S. Johnson.
Worst-case behavior og graph coloring algorithms.
In
*Proceedings 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing*, pages 513-527, Winnipeg, Canada, 1974. Utilitas Mathematica Publishing. **53**-
David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon.
Optimization by simulated annealing: An experimental evaluation; part
ii, graph coloring and number partitioning.
*Operations Research*, 39(3):378-406, 1991. **54**-
A. Johri and David W. Matula.
Probabilistic bounds and heuristic algorithms for coloring large
random graphs.
Technical report, Southern Methodist University, Dallas, Texas, 1982.
**55**-
N. K. Karmarkar, K. G. Ramakrishnan, and M. G. C. Resende.
An interior point approach to the maximum independent set problem in
dense random graphs.
In
*Proceedings of the XV Latin American Conference on Informatics I*, pages 241-260, 1989. **56**-
S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi.
Optimization by simulated annealing.
*Science*, 220(13 May 1983):671-680, 1983. **57**-
S. M. Korman.
The graph-colouring problem.
In N. Christofides, A. Mingozzi, P. Toth, and C. Sandi, editors,
*Combinatorial Optimization*, pages 211-235, New York, 1970. Wiley. **58**-
M. Kubale and B. Jackowski.
A generalized implicit enumeration algorithm for graph coloring.
*Communications of the ACM*, 28:412-418, 1985. **59**-
M. Kubale and E. Kusz.
Computational experience with implicit enumeration algorithms for
graph coloring.
In M. Nagl and J. Perl, editors,
*Proceedings of the WG'83 International Workshop on Graphtheoretic Concepts in Computer Science*, pages 167-176, Linz, 1983. Trauner Verlag. **60**-
Ludek Kucera.
Expected behavior of graph coloring algorithms.
In M. Karpinski, editor,
*Foundations of Comupation Theory 77*, volume 56 of*Lecture Notes in Computer Science*, pages 447-451, Berlin, 1977. Springer. **61**-
Ludek Kucera.
Graphs with small chromatic numbers are easy to color.
*Information Processing Letters*, 30:233-236, 1989. **62**-
Ludek Kucera.
The greedy coloring is a bad probabilistic algorithm.
*Journal of Algorithms*, 12:674-684, 1991. **63**-
E. L. Lawler.
A note on the complexity of the chromatic number problem.
*Information Processing Letters*, 5:66-67, 1976. **64**-
F.T. Leighton.
A graph coloring algorithm for large scheduling problems.
*Journal of Reasearch of the National Bureau of Standards*, 84:489-506, 1979. **65**-
E. Loukakis and C. Tsouros.
Determining the number of internal stability of a graph.
*International Journal of Computer Mathematics*, 11:207-220, 1982. **66**-
C. Lund and M. Yannakakis.
On the hardness of approximating minimization problems.
In
*Proceedings 25th ACM Symposium on Theory of Computing*, page (submitted), New York, NY, 1993. ACM. **67**-
D. G. Matula.
Bounded color functions on graphs.
*Networks*, 2:29-44, 1972. **68**-
D. W. Matula, G. Marble, and J. D. Isaacson.
Graph theory and computing.
In R. C. Read, editor,
*Graph coloring algorithms*, pages 109-122, New York, NY, 1972. Academic Press. **69**-
David Matula and Ludek Kucera.
An expose-and-merge algorithm and the chromatic number of a random
graph.
In M. Karonski, J. Jaworski, and A. Rucinski, editors,
*Random Graphs'87*, pages 175-187. John Wiley and Sons, 1990. **70**-
C. Morgenstern and H. Shapiro.
Heuristics for rapidly four-coloring large planar graphs.
*Algorithmica*, 6:869-891, 1991. **71**-
Craig Morgenstern and Harry Shapiro.
Coloration neighborhood structures for general graph coloring.
In
*First Annual ACM-SIAM Symposium on Discrete Algorithms*, 1990. **72**-
George L. Nemhauser and Les E. Trotter.
Vertex packings: Structural properties and algorithms.
*Mathematical Programming*, 8:232-248, 1975. **73**-
Hideo Ogawa.
Labeled point pattern matching by delaunay triangulation and maximal
cliques.
*Pattern Recognition*, 19(1):35-40, 1986. **74**-
R.J. Opsut and Fred S. Roberts.
On the fleet maintenance, movile radio frequency, task assignment and
traffic phasing problems.
In G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Lesniak-Foster, and
D.R. Lick, editors,
*The Theory and Applications of Graphs*, pages 479-492, New York, NY, 1981. John Wiley & Sons. **75**-
P. M. Pardalos and G. P. Rodgers.
A branch and bound algorithm for the maximum clique problem.
*Computers and Operations Research*, 19:363-375, 1992. **76**-
P. M. Pardalos and J. Xue.
The maximum clique problem.
*Journal of Global Optimization*, page (to appear), 1993. **77**-
J. Peemöller.
A correction to Brélaz's modification of Brown's coloring
algorithm.
*Communications of the ACM*, 26:595-597, 1983. **78**-
B. Pittel.
On the probable behaviour of some algorithms for finding the
stability number of a graph.
*Mathematical Proceedings of the Cambride Philosophical Society*, 92:511-526, 1982. **79**-
Robert E. Tarjan and A.E. Trojanowski.
Finding a maximum independent set.
*SIAM Journal on Computing*, 6:266-283, 1977. **80**-
J. S. Turner.
Almost all -colorable graphs are easy to color.
*Journal of Algorithms*, 9:63-82, 1988. **81**-
P.J.M Van Laarhoven and E.H.L. Aarts.
*Simulated Annealing: Theory and Practice*. Kluwer Academic Publishers, Dordrrecht, The Netherlands, 1987. **82**-
D.J.A. Welsh and M.B. Powell.
An upper bound on the chromatic number of a graph and its application
to timetabling problems.
*Computer Journal*, 10:85-86, 1967. **83**-
A. Wigderson.
Improving the performance guarantee of approximate graph coloring.
*Journal of the Association for Computing Machinery*, 30:729-735, 1983. **84**-
M. R. Williams.
The coloring of very large graphs.
In
*Combinatorial Structures and their Applications*, pages 477-478, New York, 1970. Gordon and Breach. **85**-
D. C. Wood.
A technique for coloring a graph applicable to large scale
time-tabling problems.
*The Computer Journal*, 3:317-319, 1969. **86**-
G. Yu, O. Goldschmidt, and H. Chen.
Clique, independent set, and vertex cover in geometric graphs.
ORSA/TIMS Presentation, San Francisco, CA, 1992.
**87**- G. Yu, P. Kouvelis, and Luo. A weighted vertex packing problem for specially structured geometric graphs arising in the design of electronic testing fixtures. ORSA/TIMS Presentation, San Francisco, CA, 1992.

Thu Oct 27 21:43:48 EDT 1994