An Investigation of Several Branching Functions in a Branch and Bound Algorithm for the Chromatic Number Problem.

Abstract

The chromatic number problem is to determine the minimum number of colors to assign to the vertices of a graph such that no connected vertices are assigned the same color. This paper presents a branch and bound solution to the chromatic number problem and investigates five different branching functions. Additionally, a method of coloring very sparse graphs is presented which divides a graph into biconnected components and reduces the time required to color the graph. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1980
Accession Number
ADA097330

Entities

People

  • Ronald Ernest Rautenberg

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Demographic Cohorts
  • Digital Computers
  • Graph Theory
  • Mathematics
  • Notation
  • Polynomials
  • Programming Languages
  • Random Number Generators
  • Trees (Data Structures)
  • United States

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.