Experimental and Efficient Algorithms

This proceedings volume contains the accepted papers and invited talks p- sented at the 4th International Workshop of E?cient and Experimental Al- rithms (WEA 2005), that was held May 10-13, on Santorini Island, Greece. The WEA events are intended to be an international forum for research on the design, analysis and especially the experimental implementation, evaluation and engineering of algorithms, as well as on combinatorial optimization and its applications. The?rstthreeworkshopsinthisserieswereheldinRiga(2001),MonteVerita (2003) and Rio de Janeiro (2004). Thisvolumecontains3invitedpapersrelatedtocorrespondingkeynotetalks: by Prof. Christos Papadimitriou (University of California at Berkeley, USA), Prof. David Bader (University of New Mexico, USA) and Prof. Celso Ribeiro (University of Rio de Janeiro, Brazil). This proceedings includes 54 papers (47 regular and 7 short), selected out of a record number of 176 submissions. Each paper was reviewed by at least 2 Program Committee members, while many papers got 3 or 4 reviews. A total number of 419 reviews were solicited, with the help of trusted external referees.In addition to the 54 papers included in this volume, 6papers were accepted as poster presentations: these papers were published in a separate poster p- ceedings volume by CTI Press and a major publisher in Greece, "Ellinika Gr- mata." The presentation of these posters at the event was expected to create a fruitful discussion on interesting ideas.