Graph coloring is about allocating resources that can be shared except where there are certain pairwise conflicts between recipients. The simplest coloring algorithm that attempts to conserve resources is called first fit. Interval graphs are used in models for scheduling (in computer science and operations research) and in biochemistry for one-dimensional molecules such as genetic material. It is not known precisely how much waste in the worst case is due to the first-fit algorithm for coloring interval graphs. However, after decades of research the range is narrow.
Download count: 0
- Partial requirement for: Ph.D., Arizona State University, 2010Note typethesis
- Includes bibliographical references (p. 60-62)Note typebibliography
- Field of study: Mathematics