Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does anyone have any real world applications for edge coloring in graphs?

share|improve this question
1  
This is an interesting question +1 –  Alexander Gruber Mar 5 '13 at 2:55
    
It's not much, but from Wikipedia: "Edge colorings have applications in scheduling problems and in frequency assignment for fiber optic networks" –  Arkamis Mar 5 '13 at 2:58
add comment

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
1  
Ahh yes, from that page I got sports scheduling...I am huge fan of the NFL, but never realized they used edge coloring to schedule each season, nor the fact the Vizing's Theorem guarantees a bye week for each team... –  M0RF3US Mar 5 '13 at 3:06
    
Round Robin tournaments can also use edge coloring to schedule rounds and games. –  M0RF3US Mar 5 '13 at 3:06
    
Oh, so you already checked that out? do you want me to keep it or take it down then? –  Bananarama Mar 5 '13 at 3:11
    
Keep it, I hadn't seen it until you posted and I checked. Thanks! –  M0RF3US Mar 5 '13 at 3:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.