Books
in black and white
Main menu
Share a book About us Home
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): сombinatorialoptimi2012.pdf
Previous << 1 .. 74 75 76 77 78 79 < 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 Systems—I. 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};
Previous << 1 .. 74 75 76 77 78 79 < 80 > 81 82 83 84 85 86 .. 156 >> Next