ERNESTO MARTINS'
Personal Home Page

Recent Results on Ranking Shortest Paths:


June 24th, 1998

A first version of the joint paper with Marta Pascoal and José Luis Santos, "The K shortest loopless paths problem" is finished and online.

June 19th, 1998

A first version of the joint paper with Marta Pascoal and José Luis Santos, "The K shortest loopless paths problem" is almost finished and it will be online in a very near future.

June 16th, 1998

A first version of the joint paper with Marta Pascoal and José Luis Santos, "The K shortest paths problem" is finished and online (for while).

May 20th, 1997

Entitled "A new algorithm for ranking loopless paths" the first draft of a joint paper with Marta Pascoal and José Luis Santos, is now (and for while) online.

May 13th, 1997

Marta, Zé Luis and myself developed a new algorithm for ranking loopless paths. It has nothing of similar with MS algorithm. The first draft of the paper is done (some minor revisions are needed); so I hope to have the paper on line in very few days.


October 17th, 1996

A second C code version for Eppstein algorithm is finally online.

The first draft of the paper describing MS algorithm is finally finished and online.


September 6th, 1996

Two C codes for Yen's algorithm are on line since two days ago. The second code was intended to be a computational improvement to the first one, but it seems to be no more effient than the first code. Marta is the author of both codes.

The first draft of the paper describing MS algorithm it is almost finished. It is only missing the Computational Experiments paragraph.


March 29th, 1996

The first C code version for Eppstein's algorithm is on line since a couple of months ago. Zé Luis wrote a second C code version too for this algorithm which will be on line as soon as he has a little free time.

The draft of the paper continues to be a project yet... I think to begin by all next month. (It is a promise). However I hope to be at IFORS 96 in Vancouver with a talk about the algorithm. (My registration followed yesterday).

Marta is drawing her attention for the loopless path problem. She wrote a C code for Yen's algorithm which will be on line as soon as she has a little free time.


November 19th, 1995

The C code for MS algorithm is on line since some days ago. In the meanwhile the research team is reinforced with Marta and the draft of the paper is a project yet... Now I am being the lazy...

We are also preparing the C code for Eppstein's algorithm, in order to put it on line. I hope the work is finished very soon...


September 1st, 1995

The C code for the algorithm is now ready, but... Zé Luis have to write the "HELP" file... and he is being a little lazy...

I am begining to write the first draft of the paper.

In the meanwhile, the research team (I and Zé Luis) is working on a new algorithm for the ranking of shortest trees.


April 11th, 1995

At the moment I am working with Jos Luis Esteves dos Santos, on the last published K shortest paths ranking algorithm (see published papers), to decrease its complexity in order the required memory space.

Interesting results have been recently obtained which we intend to submit for publication as soon as possible. (April 11, 1995)



Computational Experiments with the new Algorithm.

(The new algorithm is being called MS algorithm)

(Means for 10 Random Generated Networks -- 10000 Nodes)

Last Update: May 20, 1997
  1. Execution Times: (GIF - 9171K) / (PS - 7348K)
  2. Number of Nodes Growth: (GIF - 9135K) / (PS - 10484K)
  3. Number of Elementary Paths (%) until K: (GIF - 8026K) / (PS - 7389K)
  4. Number of Problems (%) that run until K: (GIF - 10255K) / (PS - 7253K)


    BACK


    HOME PAGE