Chapter 9
Superperfect graphs
Martin Charles Golumbic
Publisher Summary
This chapter focuses on a notion of perfection in weighted graphs. In the process, a more general type of coloring the vertices of a graph is introduced, suggesting many significant applications. The concept of superperfection, introduced is motivated by the shipbuilding problem. An interval coloring of a weighted graph (G; w) maps each vertex x onto an (open) interval Ix of the real line of width (or measure) w(x) such that adjacent vertices are mapped to disjoint intervals. The chapter discusses the shipbuilding problem, banquet problem, and computer storage optimization. Most compilers maintain a one-to-one mapping between the variables in a program and their locations in ...
