04 November 2007

All shortest paths

I cooked up this while correcting some assignments:

You are given a digraph (as adjacency lists), a source node and a target node. Find the smallest subgraph that contains all the shortest paths from the source to the target.

And here's another one:

You are given a digraph and a partition of its nodes. Test if the partition has the following property: if x->y then for all x' in the same class as x there is a y' in the same class as y such that x'->y'.

No comments:

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.