Give a greedy algorithm to make a reasonable attempt at coloring a graph in ?(? +...

Give a greedy algorithm to make a reasonable attempt at coloring a graph in ?(? + ?) time. In pseudo code

Expert Solution

We can use greedy algorithm to color a graph. Since this is a Non polynomial complete task, we can't have the choice of using minimum colors, but we can surely set an upper limit using greedy algorithm.

So, the algorithm is-

Fill color in 1st vertice with the 1st colour we have.

And now for the rest of the vertices do this-

Choose the current vertice, fill it with color that has the least value numerically and hasn't been used before on any vertices that are located adjacently to it. Use a different color and mark it as used.

Below is the code for the given algorithm/pseudocode. Time complexity- O(V+E).

OUTPUT-

venereology answered 5 months ago

Give an example that shows the greedy algorithm for activity selection that picks the activity with...

Give an example that shows the greedy algorithm for activity selection that picks the activity with the smallest start time first (and continues in that fashion) does not solve the activity selection problems correctly. Please show your work! I will rate quality answers. Thank you.

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph...

Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. (It should not output all cycles in the graph, just one of them.) The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges.

Describe the A* algorithm. Give one search example: give one graph as example with a heuristic...

Describe the A* algorithm. Give one search example: give one graph as example with a heuristic function for each node; give the start node and goal node; apply the A* algorithm on this problem. Show the steps and sequence of nodes visited in order that leads to the optimal solution.

Code in C# please. Write a program that will use the greedy algorithm. This program will...

Code in C# please. Write a program that will use the greedy algorithm. This program will ask a user to enter the cost of an item. This program will ask the user to enter the amount the user is paying. This program will return the change after subtracting the item cost by the amount paid. Using the greedy algorithm, the code should check for the type of bill. Example: Cost of item is $15.50 User pays a $20 bill $20...

Give an algorithm that constructs an undirected connected graph, which allows for labeling of the n...

Give an algorithm that constructs an undirected connected graph, which allows for labeling of the n vertices u - v <= k for every edge (u,v), where k is some constant. All nodes have a unique label.

In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem. (a)...

In C++ or Java Write the Greedy programming Algorithm for the 0-1 Knapsack problem. (a) No fraction allowed Max Weight W= 9 item 1: profit $20, weight 2, prof/weight=$10 item 2: profit $30, weight 5, prof/weight=$6 item 3: profit $35, weight 7, prof/weight=$5 item 4: profit $12, weight 3, prof/weight=$4 item 5: profit $3, weight 1, prof/weight=$3

What is the greedy choice being made by Kruskal’s algorithm? Show that this choice results in...

What is the greedy choice being made by Kruskal’s algorithm? Show that this choice results in an optimal substructure.

Question on greedy algorithm. A sculptor starts with n metal pieces which are to be pairwise...

Question on greedy algorithm. A sculptor starts with n metal pieces which are to be pairwise forged together until one piece (the sculpture) emerges. The forging process melds two pieces into one with an energy cost directly proportional to the product of the sizes of the two pieces forged together. For example, melding three pieces of sizes x, y and z could be done in different orders, yielding different costs ( x*y + x*y*z OR x*z + x*z*y OR y*z...

java code for scheduling problem (start time,end time , profite) using greedy algorithm

Consider P|rj, prec|Cmax. Show that the greedy algorithm is a 2-approximation. (It pertains to Scheduling Theory,...

Consider P|rj, prec|Cmax. Show that the greedy algorithm is a 2-approximation. (It pertains to Scheduling Theory, Algorithms, and Systems.)

Question