Home - mishraj343/Parallel-Programming-Solution-to-the-Graph-Coloring-Problem GitHub Wiki

Welcome to the Parallel-Programming-Solution-to-the-Graph-Coloring-Problem wiki!

We introduce a classical problem in graph theory called The graph coloring problem. Basically, the procedure graph coloring problem is to assign colors to the vertices of a graph in a such way that no two vertices connected by an edge share the same color. Our aim is to use as few number of colors as possible.It is easy to observe that the map-coloring problem stated above can be modeled as a graph coloring problem. Such a graph, one which corresponds to some kind of map, is in fact called a planar graph. Today, it is a well known fact that 4 colors are enough to color any planar graph. The graph coloring problem has a central role in computer science. It models many significant real-world problems, or arises as part of a solution for other important problems. The next few paragraphs highlight some of the major application areas.

Time Tabling and Scheduling

Many scheduling problems involve allowing for a number of pairwise restrictions on which jobs can be done simultaneously. For instance, in attempting to schedule classes at a university, two courses taught by the same instructor can not be scheduled for the same time slot. Similarly, two courses that are required by the same group of students should not be scheduled for the same time slot. The problem of determining the minimum number of time slots needed subject to these restrictions can be modeled by the graph coloring problem.

Frequency Assignment

Another example is the problem of assigning frequencies to mobile radios and other users of electromagnetic spectrum. In the simplest case, two customers that are sufficiently close must be assigned different frequencies, while those that are distant can share frequencies. The problem of minimizing the number of frequencies has been modeled as a graph coloring problem. Register Allocation One of the issues involved during program execution is register allocation. The register allocation problem denotes the problem of assigning variables to a limited number of hardware registers.

Printed Circuit Testing This is an example in which graph coloring is used to speed up the testing of printed circuit boards for unintended short circuits caused by stray lines of solder . Numerical Computation

Graph coloring arises as part of the solution for many problems in computational science . It has also reported applications in optimization and parallel numerical methods . Given its importance, one is interested in solving the graph coloring problem in a fastest and cost effective way possible. This goal is particularly important when one deals with graphs of very large size. The need for faster solutions and for solving larger-size problems arises in many other applications also. At present, technology has reached a stage where the fastest cycle time of a processor in a computer seems to be approaching fundamental physical limitations beyond which no improvement is possible. This, coupled with a steady decline in hardware cost, has led to the use of multiprocessor parallel computers for achieving increased computational speed. Currently, commercially available multiprocessor parallel computers are based on distributed-memory, shared-memory, or distributed-shared-memory architectures. The target computer of this study, the Cray Origin 2000, is an example of the last type. An on-line description of the architecture of the Origin 2000 installed at Parallab states the following. “In effect, distributed-shared-memory architecture means that the memory is physically distributed and resides on the processors. However, for operational purposes, the system behaves as a shared memory computer with the operating system taking care of maintaining memory consistency. Thus any processor can use the total amount of memory.”