Scribd
Upload
46 views11 pages

AOA Backtracking Branch and Bound Graph Colouring Algo

The document provides an overview of algorithms related to graph coloring, including the definition of the chromatic number and its NP-completeness. It discusses the graph coloring problem as both a decision and optimization problem, with various applications such as timetable design and mobile radio frequency assignment. Additionally, it references key literature in the field of algorithms.

Uploaded by

aryavinodk83
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
46 views11 pages

AOA Backtracking Branch and Bound Graph Colouring Algo

The document provides an overview of algorithms related to graph coloring, including the definition of the chromatic number and its NP-completeness. It discusses the graph coloring problem as both a decision and optimization problem, with various applications such as timetable design and mobile radio frequency assignment. Additionally, it references key literature in the field of algorithms.

Uploaded by

aryavinodk83
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Analysis of Algorithms

CE – SE –SEM IV
Suneha Raut
SIES Graduate School of Technology

1
2
Overview
• General Method

• Backtracking: N-queen problem

• Sum of subsets

• Graph coloring

• Branch and Bound: Travelling Salesperson Problem

• 15 Puzzle problem

3
Graph Colouring Algorithm

• Graph coloring refers to the problem of coloring vertices of a


graph in such a way that no two adjacent vertices have the
same color. This is also called the vertex coloring problem. If
coloring is done using at most m colors, it is called m-coloring.

4
• Chromatic Number:
• The minimum number of colors needed to color a graph is
called its chromatic number. For example, the following can be
colored a minimum of 2 colors.

5
The problem of finding a chromatic number of a given graph
is NP-complete.
Graph coloring problem is both, a decision problem as well as
an optimization problem.
• A decision problem is stated as, “With given M colors and
graph G, whether a such color scheme is possible or not?”.

• The optimization problem is stated as, “Given M colors and


graph G, find the minimum number of colors required for graph
coloring.”

6
Applications of Graph Coloring Problem
• Design a timetable.
• Sudoku
• Register allocation in the compiler
• Map coloring
• Mobile radio frequency assignment:

7
8
9
References
• books:
• 1 T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms”, 2nd
Edition, PHI Publication 2005.
• Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms”
University Press.

10
•THANK YOU

11

You might also like