Cliques and Colorings Bibliography

December 2, 1992

This document prints out the bibliography ccreview.bib. This bibliography contains a number of important references, but is by no means a complete survey of the field. Send additions and comments to challenge@dimacs.rutgers.edu.

References

[1] E.H.L. Aarts and J.H.M Korst. Simulated Annealing and Boltzmann Machines. John Wiley & Sons, Chichester, U.K., 1989.

Key: AaKo89 Annotation: Book providing an overview of simulated annealing techniques and issues.

[2] E.A. Akkoyunlu. The enumeration of maximal cliques of large graphs. SIAM Journal on Computing, 2(1):1–6, 1973.

Key: Ak73 Annotation: An implicit enumeration routine for listing all maximal cliques.

[3] K. Appel and W. Haken. Every planar map is 4-colorable – 1: Discharging. Illinois Journal of Mathematics, 21:421–490, 1977.

Key: ApHa77a

[4] K. Appel and W. Haken. Every planar map is 4-colorable – 2: Reducibility. Illinois Journal of Mathematics, 21:491–567, 1977.

Key: ApHa77b

[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.

Key: ALMSS92 Annotation: Strengthens result of [6]: there is an ϵ such that no polynomial-time heuristic for clique can be guaranteed to come within a factor of n^{ϵ} of optimal unless P = NP.

[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.

Key: ArSa92 Annotation: Shows that no polynomial-time heuristic for clique can be guaranteed to come within a constant factor of optimal unless P = NP.

[7] Luitpold Babel. Finding maximum cliques in arbitrary and in special graphs. Computing, 46:321–341, 1991.

Key: Ba91 Annotation: Contains a branch and bound algorithm for maximum clique. Analyzes when branch and bound tree has a polynomial number of nodes so gives a number of polynomially solvable special cases. Bounds based on graph coloring.

[8] Egon Balas and H. Samuelsson. A node covering algorithm. Naval Research Logistics Quarterly, 24(2):213–233, 1977.

Key: BaSa77 Annotation: A polyhedral approach to vertex packing.

[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.

Key: BaXu91 Annotation: A branch and bound algorithm for maximum weighted cliques. This work is a generalization of [10]. The algorithm is based on a method for finding weighted colorings of triangulated graphs.

[10] Egon Balas and Chang Sung Yu. Finding a maximum clique in an arbitrary graph. SIAM Journal on Computing, 15(4):1054–1068, 1986.

Key: BaYu86 Annotation: A branch and bound procedure for maximum clique. Based on coloring triangulated graphs. Computational experiments.

[11] Jean-Pierre Barthélemy and Alain Guénoche. Trees and Proximity Representations. John Wiley and Sons, New York, NY, 1991.

Key: BaGu91 Annotation: Chapter 5 contains an application for clique. A set of items (biological species, archeological artifacts) need to be classified into a tree. A distance is found between all items. If the resulting distance is a tree distance, then that is the tree. Otherwise, form a graph where each node is a partition and two nodes are connected if they are tree–compatible (an inclusion relation). The only partitions permitted are those that represent a cut in the distance metric. A clique is a set of partitions that is compatible with a tree.

[12] B. Berger and J. Rompel. A better permance guarantee for approximate graph coloring. Algorithmica, 5:459–466, 1990.

Key: BeRo90 Annotation: Construction for graph coloring that in the worst case uses O(n(log log n/ log n)^{3}) times the optimal number of colors.

[13] A. Blum. An Õ(n^{0.4})-approximation algorithm for 3-coloring (and improved approximation algorithms for k-coloring). In Proceedings 21st ACM Symposium on Theory of Computing, pages 535–542, New York, 1989. ACM.

Key: Bl89 Annotation: See title.

[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.

Key: Bl90 Annotation: Shows that how to get an n^{.}375 coloring of a 3colorable graph in polynomial time. Also considers models of random 3-colorable graphs where 3-colorings can be efficiently found with high probabibity.

[15] B. Bollobás. The chromatic number of random graphs. Combinatorica, 8:49–56, ???

Key: Bo

[16] B. Bollobás and P. Erdös. Cliques in random graphs. Mathematical Proceedings of the Cambride Philosophical Society, 80:419–427, 1976.

Key: BoEr76 Annotation: In a random graph, the clique size is 2log n.

[17] B. Bollobas and A. Thomason. Random graphs of small order. Annals of Discrete Math., 28:47–97, 1985.

Key: BoTh85 Annotation: Discusses estimates of chromatic number and optimal clique size in random graphs and reports on an implementation of a variant of the coloring algorithm from [54].

[18] D. Brélaz. New methods to color vertices of a graph. Communications of the ACM, 22:251–256, 1979.

Key: Br79 Annotation: Successive augmentation approach to graph coloring. DSATUR chooses the vertex adjacent to the largest number of distinctly colored vertices. Paper also discusses an implicit enumeration scheme for finding an optimal coloring using some of the principles of DSATUR to guide the search.

[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.

Key: BCKT89

[20] Coen Bron and Joep Kerbosch. Finding all cliques of an undirected graph. Communications of the ACM, 16(9):575–577, 1973.

Key: BrKe73 Annotation: An implicit enumeration algorithm for listing all cliques in a graph. Includes easily translated code.

[21] R. J. Brown. Chromatic scheduling and the chromatic number problem. Management Science, 19:451–463, 1972.

Key: Br72 Annotation: Implicit enumeration algorithm [not seen].

[22] R. Carraghan and P. M. Pardalos. An exact algorithm for the maximum clique problem. Operations Research Letters, 9:375–382, 1990.

Key: CaPa90 Annotation: Implicit enumeration algorithm, designed to work well on sparse graphs. Paper includes a program listing.

[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.

Key: Ce85 Annotation: With [56], one of the two papers that first suggested the idea of simulated annealing, here applied to the traveling saleman problem.

[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.

Key: Ch82 Annotation: First (?) paper describing graph coloring and register allocation and graph coloring

[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.

Key: CACCHM81 Annotation: First to apply coloring approach to register allocation in an experimental compiler at IBM

[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.

Key: CHD87 Annotation: Simulated annealing applied to graph coloring.

[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.

Key: ChHe84

[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.

Key: ChHe90 Annotation: A more extensive approach to register allocation that uses a number of different factors before applying a coloring heuristic.

[29] N. Christofides. An algorithm for the chromatic number of a graph. Computer Journal, 14:38–39, 1971.

Key: Ch71 Annotation: Implicit enumeration algorithm [not seen].

[30] N. Christofides. Graph Theory: An Algorithmic Approach. Academic Press, London., 1975.

Key: Ch75 Annotation: Contains an implicit enumeration algorithm, with a bug reported in [58].

[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.

Key: CEG88 Annotation: Very large and complete (circa 1988) bibliography of the state of simulated annealing.

[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.

Key: CoGr73 Annotation: Implicit enumeration algorithm based on Zykov’s theorem.

[33] D. De Werra. An introduction to timetabling. European Journal of Operations Research, 19:151–162, 1985.

Key: De85 Annotation: A survey of techniques and papers for solving timetabling problems, including a section on graph coloring techniques.

[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.

Key: DyFr89 Annotation: Explores the possibility of coloring random k– colorable graphs in polynomial time.

[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.

Key: FGLSS91 Annotation: First paper to show that no polynomial-time heuristic for clique can be guaranteed to come within a constant factor of optimal unless an unlikely conjecture held (in this case, NP contained in P^{log log(n})).

[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.

Key: FRS93 Annotation: Heuristic based on randomized search, somewhat on the principles suggested in [54].

[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.

Key: FuSu92 Annotation: Widens class of models for random k-colorably graphs for which efficient k-coloring algorithms can be found.

[38] Andreas Gamst. Some lower bounds for a class of frequency assignment problems. IEEE Transactions of Vehicular Echnology, 35(1):8–14, 1986.

Key: Ga86 Annotation: An application for maximum weighted clique. Lower bounds on the number of frequencies required for the assignment of frequencies to mobile radio telephone systems are found by finding large cliques in an associated graph.

[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.

Key: GJS76 Annotation: Application mentioned in title yields interesting class of graphs for which heuristics are analyzed.

[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.

Key: GaJo76 Annotation: Show that there exists no algorithm that colors a graph using within two times the optimal number of colors unless P=NP.

[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.

Key: GaJo79 Annotation: ”The Bible.” An indispensible guide to NP– completeness and related issues. Updated by Johnson’s semiregular column in the Journal of Algorithms.

[42] L. Gerhards and W. Lindenberg. Clique detection for nondirected graphs: Two new algorithms. Computing, 21:295–322, 1979.

Key: GeLi79 Annotation: Two branch and bound algorithms for finding maximum clique are presented.

[43] Fred Glover. Tabu search, part 1. ORSA Journal on Computing, 1:190– 206, 1989.

Key: Gl89 Annotation: A tutorial on tabu search for combinatorial optimization problems.

[44] D. E. Goldberg. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, Reading, MA, 1989.

Key: Go89 Annotation: An introduction to genetic algorithms, although with nothing specifically about graph coloring or clique finding.

[45] M. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Acadmeic Press, New York, NY, 1980.

Key: Go80 Annotation: A wonderful graph theory book with an emphasis on perfect graphs.

[46] G.R. Grimmet and C.J.H. McDiarmid. On colouring random graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 77:313–324, 1975.

Key: GrMc75 Annotation: Analysis of a simple successive approximation algorithm for coloring random graphs.

[47] M. M. Halldórsson. A still better performance guarantee for approximate graph coloring. Technical Report 91–35, DIMACS, New Brunswick, NJl, 1990.

Key: Ha90 Annotation: Heuristic for graph coloring that has current record for “good” worst-case behavior: O(n(log log n)^{2}/(log n)^{3} times the optimal number of colors.

[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.

Key: HPV92 Annotation: Generators from many applications. Should be available via anonymous FTP from DIMACS (in

pub/challenge/graph/contributed/pardalos).

[49] A. Hertz and D. De Werra. Using tabu search techniques for graph coloring. Computing, 39:345–351, 1987.

Key: HeDe87 Annotation: A tabu search approach to graph coloring problems

[50] Mark Jerrum. Large cliques elude the metropolis process. Random Structures and Algorithms, 3(4):347–360, 1992.

Key: Je92 Annotation: This paper shows that simulated annealing needs exponential time to find a clique within a factor of 2 of the largest for random graphs.

[51] David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256–278, 1974.

Key: Jo74a Annotation: Introduced “approximation algorithm” terminology; includes worst-case analysis of simple heuristics for clique and graph coloring. The graph coloring results were extended in [52].

[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.

Key: Jo74b Annotation: Shows that a number of simple successive augmentation heuristics for graph coloring can do very poorly.

[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.

Key: JAMS91 Annotation: A very thorough examination of the application of simulated annealing to graph coloring. Examines randomly generated graphs and random ”geometric” graphs.

[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.

Key: JoMa82

[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.

Key: KRR89

Annotation: Interior point heuristics based on convex quadratic programming.

[56] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Optimization by simulated annealing. Science, 220(13 May 1983):671–680, 1983.

Key: KGV83

Annotation: First popular account of using simulated annealing for combinatorial optimization.

[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.

Key: Ko79

Annotation: Implicit enumeration algorithm [not seen].

[58] M. Kubale and B. Jackowski. A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM, 28:412–418, 1985.

Key: KuJa85

Annotation: Presents algorithm and gives experimental comparison to approaches of [21, 30, 18, 57].

[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.

Key: KuKu83 Annotation: Experiments with implicit enumeration algorithm [not seen].

[60] Ludek Kučera. 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.

Key: Ku77

[61] Ludek Kučera. Graphs with small chromatic numbers are easy to color. Information Processing Letters, 30:233–236, 1989.

Key: Ku89 Annotation: This paper extends the result of [80] on coloring (1 − ϵ) log n–colorable graphs to o(\sqrt{n/ log n})–colorable graphs.

[62] Ludek Kučera. The greedy coloring is a bad probabilistic algorithm. Journal of Algorithms, 12:674–684, 1991.

Key: Ku91 Annotation: Shows that a natural randomization of the greedy coloring is bad by giving a O(n^{ϵ})–colorable random graph that is colored by the greedy algorithm using almost surely at least Ω(n/ log n) colors.

[63] E. L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5:66–67, 1976.

Key: La76 Annotation: Reduces worst case running time to O(2^{n}) from O(n!) at cost of using exponential space.

[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.

Key: Le79

[65] E. Loukakis and C. Tsouros. Determining the number of internal stability of a graph. International Journal of Computer Mathematics, 11:207– 220, 1982.

Key: LoTs82 Annotation: An implicit enumeration algorithm for finding maximum cliques.

[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.

Key: LuYa93 Annotation: Shows that there is an ϵ such that no polynomial-time graph coloring heuristic can be guaranteed to get within a factor of |V |^{ϵ} of the optimal number of colors unless P = NP.

[67] D. G. Matula. Bounded color functions on graphs. Networks, 2:29–44, 1972.

Key: Ma72 Annotation: Proposes graph coloring heuristic, analyzed in [52].

[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.

Key: MMI72 Annotation: Defines and experimentally analyzes various graph coloring heuristics, including ones involving interchanges of colors.

[69] David Matula and Ludek Kučera. 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.

Key: MaKu90 Annotation: Proves a bound on the chromatic number of a random graph G(n, p) to be (1 + o(1))n/2 log_{\frac{1}{1−pn}}, as did [15].

[70] C. Morgenstern and H. Shapiro. Heuristics for rapidly four–coloring large planar graphs. Algorithmica, 6:869–891, 1991.

Key: MoSh91

[71] Craig Morgenstern and Harry Shapiro. Coloration neighborhood structures for general graph coloring. In First Annual ACM–SIAM Symposium on Discrete Algorithms, 1990.

Key: MoSh90 Annotation: Gives a robust neighborhood structure for local search for graph coloring, with applicability to tabu search and simulated annealing.

[72] George L. Nemhauser and Les E. Trotter. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8:232–248, 1975.

Key: NeTr75 Annotation: A polyhedral approach to vertex packing. Results include any variable in the linear relaxation to the problem with value 1 occurs in a maximum vertex packing and other results.

[73] Hideo Ogawa. Labeled point pattern matching by delaunay triangulation and maximal cliques. Pattern Recognition, 19(1):35–40, 1986.

Key: Og86 Annotation: Application of maximum clique to pattern matching. Pictures made up of points are compared using a related graph. A clique represents a feasible affine transformation among the associated points.

[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.

Key: OpRo81 Annotation: A wealth of applications of graph coloring and (somewhat) cliques.

[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.

Key: PaRo92 Annotation: Uses quadratic programming for its bounding technique. Algorithm is designed to work well on dense graphs.

[76] P. M. Pardalos and J. Xue. The maximum clique problem. Journal of Global Optimization, page (to appear), 1993.

Key: PaXu93 Annotation: Extensive survey with almost 300 references. Should be available via anonymous FTP from DIMACS (in

pub/challenge/graph/contributed/pardalos.

[77] J. Peemöller. A correction to Brélaz’s modification of Brown’s coloring algorithm. Communications of the ACM, 26:595–597, 1983.

Key: Pe83 Annotation: Corrects implicit enumeration algorithm in [18].

[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.

Key: Pi82 Annotation: A number of heuristics are examined for random graphs. None get within a factor of 2.

[79] Robert E. Tarjan and A.E. Trojanowski. Finding a maximum independent set. SIAM Journal on Computing, 6:266–283, 1977.

Key: TaTr77 Annotation: An implicit enumearation algorithm for maximum clique. Worst case running time is O(2^{n/3}).

[80] J. S. Turner. Almost all k-colorable graphs are easy to color. Journal of Algorithms, 9:63–82, 1988.

Key: Tu88 Annotation: Designs fast algorithms that optimally color random graphs with a given chromatic number quickly.

[81] P.J.M Van Laarhoven and E.H.L. Aarts. Simulated Annealing: Theory and Practice. Kluwer Academic Publishers, Dordrrecht, The Netherlands, 1987.

Key: VaAa87 Annotation: A very extensive bibliography and an overview of issues in simulated annealing.

[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.

Key: WePo67 Annotation: An early heuristic for graph coloring

[83] A. Wigderson. Improving the performance guarantee of approximate graph coloring. Journal of the Association for Computing Machinery, 30:729–735, 1983.

Key: Wi83 Annotation: A modified successive approximation heuristic to reduce the worst case behavior of the heuristic.

[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.

Key: Wi70 Annotation: Proposes graph coloring heuristic, analyzed in [52].

[85] D. C. Wood. A technique for coloring a graph applicable to large scale time-tabling problems. The Computer Journal, 3:317–319, 1969.

Key: Wo69 Annotation: Proposes graph coloring heuristic, analyzed in [52].

[86] G. Yu, O. Goldschmidt, and H. Chen. Clique, independent set, and vertex cover in geometric graphs. ORSA/TIMS Presentation, San Francisco, CA, 1992.

Key: YGC92

[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.

Key: YKL92