Description

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

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.

Reuse Permissions
  • 263.52 KB application/pdf

    Download count: 0

    Details

    Contributors
    Date Created
    • 2010
    Resource Type
  • Text
  • Collections this item is in
    Note
    • Partial requirement for: Ph.D., Arizona State University, 2010
      Note type
      thesis
    • Includes bibliographical references (p. 60-62)
      Note type
      bibliography
    • Field of study: Mathematics

    Citation and reuse

    Statement of Responsibility

    by David A. Smith

    Machine-readable links