Chapter 7: Time Complexity
Q54P
Page 329
In a directed graph, the indegreeof a node is the number of incoming edges and the outdegreeis the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph G and a designated subset C of G’s nodes, is it possible to convert G to a directed graph by assigning directions to each of its edges so that every node in C has in-degree 0 or outdegree 0, and every other node in G has indegree at least 1?
Q5E
Page 322
Is the following formula satisfiable?
Q6E
Page 322
Show that is closed under union, concatenation, and complement.
Q7E
Page 322
Show that is closed under union and concatenation.
Q8E
Page 323
Let Analyse the algorithm given on page 185 to show that this language is in .
Q9E
Page 323
A triangle in an undirected graph is a . Show that , where