[Cs5500] Generalized BFS

[Karl Lieberherr]

Hi Jessie:

The answer is indeed c-1 but your algorithm is incorrect.

You need to inspect all layers between s and t and take the one of minimum
size.

-- Karl

On Thu, Nov 3, 2011 at 11:40 AM, Jessica Lowell <lowell.j at husky.neu.edu>wrote:

> Hi Ashish,
>
> For generalized BFS, the upper limit of the length x of the vs appears to
> be c - 1.
>
> To find the vs to be eliminated, you need to find the nodes adjacent to s,
> and the nodes adjacent to t.  Whichever of adj_s and adj_t has a smaller
> number of nodes, is the set of nodes to eliminate (if they have the same
> number of nodes, just pick one).
>
> - Jessie
>
-------------- next part --------------
HTML attachment scrubbed and removed