CS341 Study Guide - Deterministic Finite Automaton, Subroutine, Jack Edmonds
Document Summary
I offer an automatic 100 in the course and to anyone who can substantially improve the running time. Consider a directed acyclic graph on n vertices, with a single distinguished vertex s called the source, and a single distinguished vertex t called the sink. (in other words, a unary nfa that accepts a finite language. ) Compute the lengths of all possible paths from s to t and report them all (in any reasonable compressed form). It is known how to do this in o(ne log n) time, where e is the optimal exponent for matrix multiplication, so i"d want something significantly better than this, say o(ne). Warning: it is very easy to think you"ve solved this problem when you haven"t. Most claimed solutions i"ve seen are based on bfs or dfs and are wrong. Bfs and dfs are unlikely to work because they only are concerned with reachable vertices, not the lengths of the paths involved.
