Algoritmos Sobre Grafos

[andreu111]

 Hola, estoy haciendo una cosilla de programacion, que tiene que correr en una maquina limitada.

Estoy haciendo calculando el flujo maximo que puede tener un grafo de unos 60000 vertices y unos 3 o 4 millones de aristas. Estoy utilizando bfs(recorrido en amplitud, si no me equivoco) vamos Edmonds-karp. Representando los grafos con listas de adyacencia, ya que con matrices seria imposible(El equipo en el que tengo que correrlo es un pentium3 800Mhz con 350MB RAM + 350MB de memoria paginada).
Actualmente me funciona pero deberia rebajar el tiempo, sabeis alguna forma de optimizar este algoritmo o la representacion de grafos?

Gracias

[nsL]

 Pues mas optimo que las listas de adyacencia no se que habra, porq ya de por si son dinamicas y ocupan lo necesario y nada mas...

[Pogacha]

 Un preprosesamiento siempre ayuda, la idea seria eliminar caminos de flujo superfluos ... y según mal recuerdo usando un goloso en vez del bfs puedes mejorarlo mucho mas. No recuerdo los nombres de los algoritmos ahora mismo :(

[Vicente]

 Hola!

has mirado si en el Cormen hablan algo de optimizar EK? Un saludo!

Vicente

[andreu111]

 Esta bastante bien el Cormen, ya lo conocia pero de optimizacion del EK no he visto nada, pero he visto el push-relabel que para mi caso es bastante bueno pues con el mio tiene un coste vertices x aristas^2  y con este vertices^3 o (vertices^2) x aristas, que para mi problema es bastante bueno.

[andreu111]

 Wenas yo de nuevo, tenia una preguntilla, hay alguna manera de darle opciones al compilador(gcc) para que te haga un codigo mas eficiente para determinada maquina(en mi caso pentium 3) a parte de la -static que es para compilar incluyendo las librerias dinamicas.