Input: a directed grid graph G, a set of target points S, and an integer k...
Input: a directed grid graph G, a set of target points
S, and an integer k
Output: true if there is a path through G that visits all points in
S using at most k left turns
A grid graph is a graph where the vertices are at integer
coordinates from 0,0 to n,n. (So 0,0, 0,1, 0,2,
...0,n, 1,0, etc.) Also, all edges are between vertices
at distance 1. (So 00->01, 00->10, but not 00 to any other
vertex. Also some edges could be missing.)
Either give a polynomial time algorithm to solve this problem, or
prove this problem is NP-hard.
Homework Answers
Add Answer to:
Input: a directed grid graph G, a set of target points
S, and an integer k...
2. Consider the following problem: Input: graph G, integer k Question: is it possible to partition...
2. Consider the following problem: Input: graph G, integer k Question: is it possible to partition vertices of G into k disjoint independent sets? Is this problem polynomial or NP-complete? Explain your answer
X) (4 points) If k is a positive integer, a k-coloring of a graph G is an assignment of one of k ...
COMP Discrete Structures: Please answer completely and
clearly.
(3).
(5).
x) (4 points) If k is a positive integer, a k-coloring of a graph G is an assignment of one of k possible colors to each of the vertices/edges of G so that adjacent vertices/edges have different colors. Draw pictures of each of the following (a) A 4-coloring of the edges of the Petersen graph. (b) A 3-coloring of the vertices of the Petersen graph. (e) A 2-coloring (d) A...
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph...
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v that is an element of S provided that {u,v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of G, that is...
For a directed graph the in-degree of a vertex is the number of edges it has...
For a directed graph the in-degree of a vertex is the number of edges it has coming in to it, and the out- degree is the number of edges it has coming out. (a) Let G[i,j] be the adjacency matrix representation of a directed graph, write pseudocode (in the same detail as the text book) to compute the in-degree and out-degree of every vertex in the Page 1 of 2 CSC 375 Homework 3 Spring 2020 directed graph. Store results...
(a) Given a graph G = (V, E) and a number k (1 ≤ k ≤...
(a) Given a graph G = (V, E) and a number k (1 ≤ k ≤ n), the CLIQUE problem asks us whether there is a set of k vertices in G that are all connected to one another. That is, each vertex in the ”clique” is connected to the other k − 1 vertices in the clique; this set of vertices is referred to as a ”k-clique.” Show that this problem is in class NP (verifiable in polynomial time)...
3, (30 points) Given a directed graph G - N. E), each edge eEhas weight We, 3, (30 points) Given a directed graph...
3, (30 points) Given a directed graph G - N. E), each edge eEhas weight We, 3, (30 points) Given a directed graph G (V, E), each edgee which can be positive or negative. The zero weight cycle problem is that whether exists a simple cycle (each vertex passes at most once) to make the sum of the weights of each edge in G is exactly equal to 0. Prove that the problem is NP complete.
3, (30 points) Given...
The input to SPANNINGTREEWITHKLEAVES is a graph G and an integer K. The question asked by...
The input to SPANNINGTREEWITHKLEAVES is a graph G and an integer K. The question asked by SPAN NINGTREEWITHKLEAVES is whether G has a spanning tree with exactly K leaves. Problem 3. Show that SPANNINGTREEWITIIKLEAVES is NP-complete. Hint: There is a simple polynomial time reduction from HAMILTONIANPATH to SPANNINGTREEWITHKLEAVES.
3. Given a directed graph G < V E >, we define its transpose Gr < V.E1 > to be the graph such tha...
3. Given a directed graph G < V E >, we define its transpose Gr < V.E1 > to be the graph such that ET-{ < v, u >:< u, v >EE). In other words, GT has the same number of edges as in G, but the directions of the edges are reversed. Draw the transpose of the following graph: ta Perform DFS on the original graph G, and write down the start and finish times for each vertex in...
Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the...
Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the reverse graph G of G. 2. Run DFS on G to obtain a post number for each vertex. Assume that in the adjacency list representation of G, vertices are stored alphabetically, and in the list for each vertex, its adjacent vertices are also sorted alphabetically. In other words, the DFS algorithm needs to examine all vertices alphabetically, and when it traverses the adjacent vertices...
Let G be a directed graph on n vertices and maximum possible directed edges; assume that...
Let G be a directed graph on n vertices and maximum possible directed edges; assume that n ≥ 2. (a) How many directed edges are in G? Present such a digraph when n = 3 assuming vertices are 1, 2, and 3. You do not have to present a diagram, if you do not want to; you can simply present the directed edges as a set of ordered pairs. b) Is G, as specified in the problem, reflexive? Justify briefly....
2. Consider the following problem: Input: graph G, integer k Question: is it possible to partition vertices of G into k disjoint independent sets? Is this problem polynomial or NP-complete? Explain your answer
COMP Discrete Structures: Please answer completely and
clearly.
(3).
(5).
x) (4 points) If k is a positive integer, a k-coloring of a graph G is an assignment of one of k possible colors to each of the vertices/edges of G so that adjacent vertices/edges have different colors. Draw pictures of each of the following (a) A 4-coloring of the edges of the Petersen graph. (b) A 3-coloring of the vertices of the Petersen graph. (e) A 2-coloring (d) A...
For a directed graph the in-degree of a vertex is the number of edges it has coming in to it, and the out- degree is the number of edges it has coming out. (a) Let G[i,j] be the adjacency matrix representation of a directed graph, write pseudocode (in the same detail as the text book) to compute the in-degree and out-degree of every vertex in the Page 1 of 2 CSC 375 Homework 3 Spring 2020 directed graph. Store results...
3, (30 points) Given a directed graph G - N. E), each edge eEhas weight We, 3, (30 points) Given a directed graph G (V, E), each edgee which can be positive or negative. The zero weight cycle problem is that whether exists a simple cycle (each vertex passes at most once) to make the sum of the weights of each edge in G is exactly equal to 0. Prove that the problem is NP complete.
3, (30 points) Given...
The input to SPANNINGTREEWITHKLEAVES is a graph G and an integer K. The question asked by SPAN NINGTREEWITHKLEAVES is whether G has a spanning tree with exactly K leaves. Problem 3. Show that SPANNINGTREEWITIIKLEAVES is NP-complete. Hint: There is a simple polynomial time reduction from HAMILTONIANPATH to SPANNINGTREEWITHKLEAVES.
3. Given a directed graph G < V E >, we define its transpose Gr < V.E1 > to be the graph such that ET-{ < v, u >:< u, v >EE). In other words, GT has the same number of edges as in G, but the directions of the edges are reversed. Draw the transpose of the following graph: ta Perform DFS on the original graph G, and write down the start and finish times for each vertex in...
Problem 3 (15 points). Let G (V,E) be the following directed graph. a. 1. Draw the reverse graph G of G. 2. Run DFS on G to obtain a post number for each vertex. Assume that in the adjacency list representation of G, vertices are stored alphabetically, and in the list for each vertex, its adjacent vertices are also sorted alphabetically. In other words, the DFS algorithm needs to examine all vertices alphabetically, and when it traverses the adjacent vertices...
Most questions answered within 3 hours.
-
A college student is employed as a door-to-door newspaper
salesman. Historical data suggests that the student...
asked 40 minutes ago -
MATLAB HW 11 problem using Switch Case and Input commands
Write a script file that calculates...
asked 25 minutes ago -
Considering gravitational time dilation, calculate the time that
passes in Earth’s surface while 1 hour passes...
asked 1 hour ago -
Minitab Problem: Take the Lake Hume June rainfall data and find
use the processes outlined in...
asked 1 hour ago -
X Company is trying to decide whether to continue using old
equipment to make Product A...
asked 1 hour ago -
IN PYTHON ONLY !! Program 2: Re-work
program #5 (WeeklyHours) from the previous assignment such that...
asked 2 hours ago -
The average length of time between arrivals at a turnpike
toll-booth is 26 seconds. What is...
asked 4 hours ago -
(a) A piston at 6.1 atm contains a gas that occupies a volume of
3.5 L....
asked 5 hours ago -
Please answer true or false. Words
cannot be changed or added in to make it true...
asked 5 hours ago -
An empty test tube weighs 15.923 grams. Then,
MgCl2•6H2O is added into the test tube. After...
asked 5 hours ago -
Assume memory access is 10 units of time and disk access is
10000 units of time....
asked 5 hours ago -
1. Are all good samples random?
2. Magazines often report surveys giving statistics such as “63%...
asked 6 hours ago