## Search found 147 matches

- Sat Oct 13, 2007 5:14 pm
- Forum: Algorithms
- Topic: DAG path enumeration
- Replies:
**2** - Views:
**2166**

- Sat Oct 13, 2007 8:05 am
- Forum: Algorithms
- Topic: DAG path enumeration
- Replies:
**2** - Views:
**2166**

### DAG path enumeration

Given a DAG (directed acyclic graph), a start and end vertex, enumerate all path lengths between them. What is the fastest algorithm? The best I've seen is to use matrix multiplication which is O(n^e(logn)) where e is the exponent for matrix multiplication. Is there a O(n^2 logn) solution? n is numb...

- Tue Aug 22, 2006 10:39 pm
- Forum: Off topic (General chit-chat)
- Topic: Find Robert
- Replies:
**4** - Views:
**2852**

- Thu Aug 17, 2006 11:59 pm
- Forum: Off topic (General chit-chat)
- Topic: Find Robert
- Replies:
**4** - Views:
**2852**

### Find Robert

Robert Barrington Leigh, a competitor representing Univeristy of Toronto at World Finals 2006, has gone missing since late Sunday night (Aug 13). Lets hope for the best.

http://findrobert.com

http://findrobert.com

- Sun Aug 06, 2006 5:32 pm
- Forum: Algorithms
- Topic: minimum edge for deletion
- Replies:
**21** - Views:
**6667**

in Chinese postman you can run a min-cost matching on a general graph with vertices the odd degree vertices in the original graph and cost the shortest path between the vertices because you are allowed to count the cost of any edge more than once or twice - here you can only count the cost of an ed...

- Fri Aug 04, 2006 8:42 pm
- Forum: Algorithms
- Topic: minimum edge for deletion
- Replies:
**21** - Views:
**6667**

- Fri Aug 04, 2006 8:19 pm
- Forum: Algorithms
- Topic: minimum edge for deletion
- Replies:
**21** - Views:
**6667**

- Mon Jul 31, 2006 7:29 am
- Forum: Algorithms
- Topic: O(log n) Fibonacci
- Replies:
**4** - Views:
**2762**

- Mon Jul 31, 2006 7:24 am
- Forum: Algorithms
- Topic: Point enclosed by segments
- Replies:
**4** - Views:
**1819**

- Mon Jul 31, 2006 7:20 am
- Forum: Algorithms
- Topic: LCS again...help
- Replies:
**4** - Views:
**2027**

essentially you backtrack through your matrix. Recall that LCS is defined as: f(i,j)=max(f(i-1,j-1)+1, f(i-1,j), f(i,j-1)) if x ==y[j] =max(f(i-1,j),f(i,j-1)) if x !=y[j] hence you want to find all possible paths from f(M,N) to f(0,0), with an edge between f(i,j) and f(i-a, j-b) if the max value of ...

- Mon Jul 31, 2006 7:12 am
- Forum: Algorithms
- Topic: minimum edge for deletion
- Replies:
**21** - Views:
**6667**

this is from the IOI 2006 practice right? (or close to it anyways, since the problem asks for all vertices to have odd degree but I think the same algorithm works) http://www.ioi2006.org/practice/highways.pdf Please state your source if its different. I've come up with this algorithm, i am not sure ...

- Mon Jul 31, 2006 7:03 am
- Forum: Algorithms
- Topic: Combinations
- Replies:
**7** - Views:
**2510**

- Mon Jul 31, 2006 7:01 am
- Forum: Algorithms
- Topic: Bipartite Graph Matching
- Replies:
**14** - Views:
**4648**

- Thu Sep 29, 2005 4:02 pm
- Forum: Volume 109 (10900-10999)
- Topic: 10902 - Pick-up Sticks
- Replies:
**24** - Views:
**13329**

- Mon Mar 28, 2005 8:44 pm
- Forum: Algorithms
- Topic: USACO help
- Replies:
**7** - Views:
**3983**