References

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.