Does anyone have any real world applications for edge coloring in graphs?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Graph coloring problems arise in several computer science disciplines. One of which is register allocation during code generation in a computer programming language compiler - In case you're not a computer scientist, a compiler is a program that translates a programming language to the native low level instructions that the CPU can execute.
The CPU has several layers of memory. The computer can store data in these layers, all of which have different sizes and different access times. Three types of storage are: hard drive, RAM, and CPU registers which is a sort of small but very fast RAM which is placed physically on the CPU. Access to the hard drive is a couple of orders of magnitude slower than access to RAM. Likewise the RAM is orders of magnitude slower to access than registers.
So if you need rapid access to some data in your program, you might choose to save it in the RAM instead of on the hard drive. If it will fit (remember, registers are small) you can save it in a register and speed up the access time even more.
The CPU has a fixed number of registers, so the compiler may try to optimize the usage of registers to speed up the program. This translates into a graph coloring problem, where you need the graph to be k-colorable for a CPU with k registers.
The problem of choosing which register to save variables in, is a graph-coloring problem. Register allocation for parameter passing can be viewed as an edge-coloring problem, where the color of each edge represent the register to contain the parameter passed from the caller to the callee.
In practice though, this requires some heuristics as some processors assign special purposes to some of the registers, so you can't always rely on having all k registers available at all time.
I know very little on the subject but I am finding this very interesting: Hope it helps. http://en.wikipedia.org/wiki/Edge_coloring#Applications