Problem regarding the polynomial-time algorithm

Assignment Help Basic Computer Science

Reference no: EM13968301

1. A graph is k-colorable if each vertex can be given one of k colors, and no edge connects identically colored vertices. Give a linear-time algorithm to test a graph for two-colorability. Assume graphs are stored in adjacency-list format; you must specify any additional data structures that are needed.

2. Give a polynomial-time algorithm that ?nds rV/21 vertices that collectively cover at least three-fourths (3/4) of the edges in an arbitrary undirected graph.

3. Show how to modify the topological sort algorithm so that if the graph is not acyclic, the algorithm will print out some cycle. You may not use depth-?rst search.

4. Let G be a directed graph with N vertices. A vertex s is called a sink if, for every v in V such that s /=v, there is an edge (v, s), and there are no edges of the form (s, v). Give an O(N) algorithm to determine whether or not G has a sink, assuming that G is given by its n × n adjacency matrix.

Reference no: EM13968301

Questions Cloud

Algorithm to solve version of the problem : Suppose that walls in the maze can be knocked down, with a penalty of P squares. P is speci?ed as a parameter to the algorithm. (If the penalty is 0, then the problem is trivial.) Describe an algorithm to solve this version of the problem. What is..

Define evangeliam as it occurs in acts : Read all of the biblical book of Acts with reference the book "The Mystical Way of Evanglism" by Heath's , I need you to read in the content of thier good news relationship between DEED AND WORD. Define evangeliam as it occurs in Acts

Strategic issues analysis of a global company : Strategic Issues Analysis of a Global Company - while this is the strategy that I most admire of the Starbucks Corporation, it is also the first topic that comes to mind when asked about a major strategic issue they are currently facing: How do the..

Determine the longest unweighted path : 1. When a vertex and its incident edges are removed from a tree, a collection of sub- trees remains. Give a linear-time algorithm that ?nds a vertex whose removal from an N vertex tree leaves no subtree with more than N/2 vertices. 2. Give a linear..

Problem regarding the polynomial-time algorithm : Give a polynomial-time algorithm that ?nds rV/21 vertices that collectively cover at least three-fourths (3/4) of the edges in an arbitrary undirected graph.

Design a linear algorithm : Let G = (V, E) be an undirected graph. Use depth-?rst search to design a linear algorithm to convert each edge in G to a directed edge such that the resulting graph is strongly connected, or determine that this is not possible.

How a business should be managed may sound attractive : The stakeholder view of how a business should be managed may sound ethically attractive but could be too simplistic.

How would you respond to the director of visitor''s bureau : In light of the city's fiscal problems, what is the most likely motivation for the new charge? Will the new overhead charge achieve its objective?

Write a summary about given article : Read this article- Researchers Say Gene Changes Show Who's Gay by MAGGIE FOX, Write a summary about it

User Account

All Pages