Description
-
Draw the KMP DFA for the following pattern string: AACAAAB.
-
Construct an example where the Boyer-Moore algorithm performs poorly.
-
True or false. If true, provide a short proof. If false, give a counterexample.
-
-
If all edge capacities are distinct, the max ow is unique.
-
-
-
There exists a max ow for which there is no directed cycle on which every edge carries positive ow.
-
-
-
If all edge capacities are increased by an additive constant, the min cut remains unchanged.
-
-
Consider a variant of the Maximum-Flow problem with node capacities as follows. Let G = (V; E) be a directed graph with source s 2 V , sink t 2 V , and nonnegative node capacities cv for each node v 2 V . Given a ow f in this graph, the ow into a node is denoted by fi(v). We say that a ow is feasible if it satis es the usual ow-conservation constraints and the node-capacity constraints: fi(v) cv for all nodes.
Show how Ford-Fulkerson algorithm can be used to nd a maximum ow in a node-capacitated network.
-
Two paths in a graph are edge-disjoint if they have no edge in common.
Disjoints Path Problem: Given a digraph G = (V; E) and two nodes s and t, nd the maximum number of edge-disjoint s-t paths.
Sow how this problem can be reduced to the max ow problem.
1