Lecture Notes in Computer Science

The Third International Workshop on Experimental and E?cient Algorithms (WEA 2004) was held in Angra dos Reis (Brazil), May 25-28, 2004. TheWEAworkshopsaresponsoredbytheEuropeanAssociationforTheo- tical Computer Science (EATCS). They are intended to provide an international forum for researchers in the areas of design, analysis, and experimental eval- tion of algorithms. The two preceding workshops in this series were held in Riga (Latvia, 2001) and Ascona (Switzerland, 2003). This proceedings volume comprises 40 contributed papers selected by the Program Committee along with the extended abstracts of the invited lectures presentedbyRichardKarp(UniversityofCaliforniaatBerkeley,USA),Giuseppe Italiano (University of Rome "Tor Vergata", Italy), and Christos Kaklamanis (University of Patras, Greece). As the organizer and chair of this wokshop, I would like to thank all the authors who generously supported this project by submitting their papers for publication in thisvolume. Iamalso grateful to theinvited lecturers, who kindly accepted our invitation. For their dedication and collaboration in the refereeing procedure, I would like also to express my gratitude to the members of the Program Committee: E. Amaldi (Italy), J. Blazewicz (Poland), V.-D. Cung (France), U. Derigs (G- many), J. Diaz (Spain), M. Gendreau (Canada), A. Goldberg (USA), P. Hansen (Canada), T. Ibaraki (Japan), K. Jansen (Germany), S. Martello (Italy), C.C. McGeoch (USA), L.S. Ochi (Brazil), M.G.C. Resende (USA), J. Rolim (Sw- zerland), S. Skiena (USA), M. Sniedovich (Australia), C.C. Souza (Brazil), P.