Problem : Describe reasonable heuristic algorithms or rules for the follow- ing

Question

Problem : Describe reasonable heuristic algorithms or rules for the follow-
ing problems. For this problem, you do not need to give full implementation
details: it is enough to describe the main idea behind the algorithm or rule
in 1-2 sentences. Keep in mind that it is ok if a heuristic sometimes fails to
find the best answer.

The Graph Coloring problem is as follows: Given a graph G, we want to assign each node a `color' such that if two nodes are adjacent (connected), then they do not have the same color. For example, if you are coloring countries on a map, then two countries that share a border should have different colors. The goal of this problem is to determine the smallest number of colors required to accomplish this. This problem is known to be NP-Complete. Design a reasonable heuristic algorithm for determining the number of colors needed to color the vertices so that no two adjacent vertices have the same color.

Explanation / Answer

We can use heuristic algorithm for graph coloring

It has got theoretical and practical information.

Graph coloring is as coloring the nodes of a graph with the minimum number of colors without any two adjacent nodes having the same color.

Two heuristic algorithms are there

First Fit algorithm

–It is fastest technique.

-It assigns each vertex the lowest legal color.

-The main advantage of being very simple and fast and can be implemented to run in O(n) allocate the lowest color to the current interval that respects the constraints imposed by the intervals that have been colored.

- coloring of a set of intervals by a function h defined on the set of intervals.
The simplicity of First-Fit has made it one of the main choices for the purpose.

Degree based coloring-

It picks a vertex from an arbitrary order.

For this some rules are used.
Largest degree ordering

– choose vertex with large nos.
-Count no of vertex.

- It holds priority queue of the possible vertexes and chooses the first one.

Saturation degree ordering

- find no of adjacent colored vertex.
-Each vertex contains the number of its adjacent differently colored vertices the algorithm hold a priority queue of the possible vertexes and chooses the first one.

basic steps for heuristic algorithm is

-Compute a the no of vertces

        -Color the nodes.

-Sort the rest of the vertices in non-increasing order of the degree of saturation

-when colouring of one vertex is finished change the degree of saturation of the neighboring vertices so that the order of coloring changes

-we can use greedy technique for improvement of coloring.

       -report the colorings in each nodes.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.