Home Publications Courses Links

Game Theory

Prof. Vladimir Gurvich
Rutgers University, 2002
 This work is much related with Graph Theory, in particular the Strong Perfect Graph Conjecture.
Basically we're testing for Circulants, 2 conjectures by Bruce Reed that are closely related with the Strong Perfect Graph Conjecture. This work is still being developed.
I have received the DIMACS Winter Award for this project.

The code was written in ANSI C and works on several platforms. [source]
There is also a multi-threaded version that works with pthreads. [mt-source] (this code is a little bit outdated if compared with the single threaded version)

Metaheuristics

Prof. Celso Ribeiro
PUC-Rio, 2000
 A hybrid Metaheursitic for Minimum Sum-of-Squares Clustering problem (based on Hansen and Mladenovic work).
The implementation includes:
  • Three heuristics for initial solution.
  • Three different types of local search.
  • VNS metaheuristic.
  • GRASP-VNS metaheuristic.
The code was written in ANSI C and works on several platforms. [source]

Advanced Data Structures

Prof. Ruy Milidiu
PUC-Rio, 2000
 A study on string matching algorithms. Five methods (cited on Cormen's book) were implemented and compared:
  • Naive.
  • Rabin-Karp.
  • Automata.
  • Knuth-Morris-Pratt.
  • Boyer-Moore.
The code was written in Lua and works on several platforms. [source]

Approximation Algorithms

Prof. Marcus Poggi
PUC-Rio, 1999
 Goemans and Williamson Primal-Dual Approximation Algorithm for the Steiner Problem in graphs.
This implementation works only for VLSI graphs, but can be easily adapted for general graphs.

The base code was written in ANSI C and works on several platforms. [source]
A simple interface was also implemented to debug and to check final solutions. It uses IUP and CD to deal with interface and drawing primitives. It also works on several platforms (i.e. Windows and most common Unixes). [source]

Image Processing for Vision and Graphics

Prof. Luiz Velho
Prof. Ralph Teixeira
IMPA, 2000
 This work is about a technique to automatically render images with painterly aspect. It is based on Shiraishi and Yamaghusi's work.

Is was developed with Danilo Tuler and Diego Nehab.

More details about the project can be found here.

The code was written in C and has an interface that only works on Windows. [source]
Compiled version that works on Windows. [Windows binary]

Last Updated on January 13, 2003