# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**80**> 81 82 83 84 85 86 .. 156 >> Next

Capital Investment

27. Valenta, J. R. (1969). Capital Equipment Decisions: A Model for Optimal Systems Interfacing. M.S. Thesis, M.I.T.

Switching Current Design and Symbolic Logic

28. Roth, J. P. (1950). Algebraic Topological Methods for the Synthesis of Switching SystemsI. Trans. Amer. Math. Soc., 88, 301-326.

29. Quine, W. V. (1955). A Way to Simplify Truth Functions. Am. Math. Mon., 62, 627-631.

30. McCluskey, E. J., Jr. (1956). Minimization of Boolean Functions. Bell System Tech. Journal, 35, 1412-1444.

210

Egon Balas and Manfred W. Padberg

31. Petrick, S. R. (1956). A Direct Determination of the Redundant Forms of a Boolean Function from the Set of Prime Implicants. AFCRC-TR-56-110, Air Force Cambridge Research Centre.

32. Paul, M. C. and S. H. Unger (1959). Minimizing the Number of States in Incompletely Specified Sequential Functions. IRE Trans, on Electronic Computers, Ec-8, 356-367.

33. Pyne, I. B. and E. J. McCluskey, Jr. (1961). An Essay on Prime Implicant Tables. Siam J., 9, 604-631.

34. Cobham, A., R. Fridshal, and J. H. North (1961). An Application of Linear Programming to the Minimization of Boolean Functions. Res. Rep. RC-472, IBM.

35. Cobham, A., R. Fridshal, and J. H. North (1962). A Statistical Study of the Minimization of Boolean Functions Using Integer Programming. Res. Rep. R.C.-756, IBM.

36. Cobham, A. and J. H. North (1963). Extension of the Integer Programming Approach to the Minimization of Boolean Functions. Res. Rep. R.C.-915, IBM.

37. Root, J. C. (1964). An Application of Symbolic Logic to a Selection Problem. Opns. Res., 12, 4, 519-526.

38. Balinski, M. L. (1965). Integer Programming: Methods, Uses, Computation. Man. Sei., 12, 3, 253-313.

39. Gimpel, J. F. (1965). A Reduction Technique for Prime Implicant Tables. IEEE Trans, on Electronic Computers, EC-14, 535-541.

Information Retrieval

40. Day, R. H. (1965). On Optimal Extracting from a Multiple File Data Storage System: An Application of Integer Programming. Opns. Res., 13, 3, 489-494.

Marketing

41. Shanker, R. J., R. K. Turner, and A. A. Zoitners (1972). Integrating the Criteria for Sales Force Allocation: A Set-Partitioning Approach. Working paper #48-72-3, CSIA, C,M.U.

Political Districting

42. Garfinkei, R. S. (1968). Optimal Political Districting. Ph.D. Dissertation, Johns Hopkins University.

43. Wagner, W. H. (1968). An Application of Integer Programming to Legislative Redistricting. Presented at 34th National Meeting of ORSA.

44. Garfinkei, R. S. and G. L. Nemhauser (1970). Optimal Political Districting by Implicit Enumeration Techniques. Man. Sei., 16, B495-B508.

CHAPTER 8

The Graph-Colouring Problem

Samuel M. Korman

Operational Research Unit, Department of Industry, London

8.1 Introductory Aspects

8.1.1 Introduction to Graph Colouring

This chapter deals with the problem of colouring the vertices of a general graph using the fewest possible number of colours, subject to the condition that no two adjacent vertices are to be of the same colour. This problem is known as the graph-colouring problem (gcp), and although various heuristic procedures exist for its approximate solution (e.g. Matula, Marble, and Issacson, 1974; Wood 1969) we consider here only exact algorithms which guarantee optimal solution.

8.1.1.1 Applications of the Graph-Colouring Problem

As a means of introducing the gcp and as a simple but typical example of its application, consider a situation where it is desired to schedule school examinations into time periods, where the particular courses chosen by any one student throughout the year involve a wide range of subjects. Then it is necessary that no two examinations be scheduled into the same time period if there is any student taking both of the corresponding courses. Although one could, for example, schedule each examination into a different time period, it is often desired to determine a schedule involving the fewest time periods into which the examinations can take place. (Neufield and Tartar, 1974; Welsh and Powell, 1967; Williams, 1968; Wood, 1969).

For example, suppose seven subjects are offered, call them Xj, x2, x3, x4, x5, x6, x7, of which two or three must be chosen, and that, of the 35, say, students, eight take x2, x4, and x7, four take x6 and x7, one takes Xj and x2, two take xl5 x2, and x6, eleven take xt, x5, and x6, eight take xu x3, and x5, and one takes x3 and x4; where it is desired to establish a minimum-period examination timetable.

212

Samuel M. Korman

Figure 8.1

The above information can be represented in the form of a graph G by letting the vertices correspond to subjects, and joining by an arc any two vertices representing subjects which are jointly taken by one or more students. The graph G thus obtained can be represented as in Figure 8.1.

The problem of scheduling the examinations into the fewest time periods can then be solved by partitioning the set of vertices {x,, x2, x3, x4, x5, x6, x7} into the smallest number of disjoint subsets such that no two vertices within any subset are joined by an arc, i.e. by solving the colouring problem for the graph G, where a colour corresponds to a time period. In the above example, the minimum number of time periods is in fact four, with many different optimal schedules, a typical one being {x3, x4}; {x2, x5}; {x3, x6};

**80**> 81 82 83 84 85 86 .. 156 >> Next