## Search found 44 matches

- Mon Oct 11, 2004 11:21 pm
- Forum: Algorithms
- Topic: Does STL use Boyer-Moore?
- Replies:
**2** - Views:
**1408**

- Mon Mar 08, 2004 10:23 pm
- Forum: Algorithms
- Topic: Hungarian method
- Replies:
**1** - Views:
**1695**

hungarian method is generally for finding perfect matchings in bipartite graphs. Given a semi-matched graph, you find an augmenting path, that is, a path that starts and ends with an unmatched vertice, and all the edges alternate between matched/unmatched. So you have: unmatched->matched->unmatched-...

- Sat Jan 31, 2004 2:19 pm
- Forum: Volume 102 (10200-10299)
- Topic: 10280 - Old Wine Into New Bottles
- Replies:
**15** - Views:
**6411**

- Tue Jan 27, 2004 3:57 pm
- Forum: Volume 102 (10200-10299)
- Topic: 10299 - Relatives
- Replies:
**57** - Views:
**14071**

This program seems to work correctly for all inputs that I found here or made up. But I constantly get WA Thanks for any help [c]#include <stdio.h> #include <math.h> int prime[100000]; int pl=0; int sito(){ char p[100000]; int i,j; p[1]=1; p[2]=0; for (i=2;i<=100000;++i) if (!p ) for (j=2;j*i<100000...

- Thu Jan 22, 2004 1:48 pm
- Forum: Algorithms
- Topic: LIS, better then O(n^2)?
- Replies:
**16** - Views:
**11836**

- Mon Nov 24, 2003 7:47 pm
- Forum: Algorithms
- Topic: perfect matching in bipartite graphs
- Replies:
**0** - Views:
**974**

### perfect matching in bipartite graphs

I'm looking for a fast algorithm that finds a perfect matching in bipartite graphs. I know of algorithms of complexity O(V*E) and O(sqrt(V)*E) that find maximum matching, but they don't satisfy me. I know that there exists an algorithm O(E*logE) for perfect matching. If anyone knows it or at least k...

- Mon Oct 13, 2003 4:07 pm
- Forum: Algorithms
- Topic: Reverse Problem.....can somebody give me hints.
- Replies:
**4** - Views:
**2280**

- Sun Sep 14, 2003 2:19 pm
- Forum: Algorithms
- Topic: find if one rectangle fits into another
- Replies:
**2** - Views:
**2200**

You have to notice, that there are only 2 possibilities to fit it. One is that the two rectangles' sides are parallel to each other, and this case is easy. The other one is a bit complicated: You have to rotate the smaller rectangle, so that two opposite corners touch the bottom and top side of the ...

- Tue Sep 02, 2003 5:56 pm
- Forum: Other words
- Topic: An Important Request !!!!!!!!!!
- Replies:
**14** - Views:
**2954**

Sometimes having someones source code is useful when you want to test your program against random-generated test cases. I think some people practice this. Another thing is that people often send their buggy code to the forum, asking what's wrong in it. Then someone tells them exactly where's the bug...

- Mon Sep 01, 2003 4:35 pm
- Forum: Algorithms
- Topic: LIS, better then O(n^2)?
- Replies:
**16** - Views:
**11836**

My way to solve this problem was to build a directed graph ( if a can be transformed into b then add edge va->vb ). It's easy to notice that in such graph O(E) = O(V). Finding the longest route in a directed acyclic graph is O(V+E)(in this case = O(V)). Now about constructing the graph. Several appr...

- Sun Aug 10, 2003 10:32 am
- Forum: Algorithms
- Topic: Who know Maximal Matching Problems O(n) solution?
- Replies:
**4** - Views:
**2328**

- Fri Aug 08, 2003 12:17 pm
- Forum: Algorithms
- Topic: Can anyone suggest an algorithm for this Clock Synchro Prob?
- Replies:
**4** - Views:
**2044**

Gauss-jordan would be OK here if you were to find ANY solution. Unfortunately you have to find the one with minimal number of moves :wink: there are 4^11= 2^22 different positions, you can aply bfs here. Such graph would be very specific, so I don't know how quick this would be. I think still to slow.

- Fri Aug 08, 2003 11:47 am
- Forum: Algorithms
- Topic: Who know Maximal Matching Problems O(n) solution?
- Replies:
**4** - Views:
**2328**

- Sun Jul 27, 2003 6:03 pm
- Forum: Algorithms
- Topic: Muliple shortest Path Problem
- Replies:
**4** - Views:
**2270**

This can be done using dijkstra. When you relax an edge u->v and d[v]== d[u]+ d[u->v] then you add u to a list of 'fathers' of v. When d[v]> d[u]+ d[u->v] then you do the same, but first you clean the list. Now having such lists in all vertices, you can easily build multiple paths between 2 given on...

- Sat Jun 07, 2003 8:51 am
- Forum: Algorithms
- Topic: Negative cycle in graph
- Replies:
**11** - Views:
**4608**