Algorithms and Complexity

The papers in this volume were presented at the 5th Italian Conference on AlgorithmsandComplexity(CIAC2003). Theconferencetookplaceduring May 28-30, 2003, in Rome, Italy, at the Conference Centre of the University of Rome "La Sapienza. " CIAC started in 1990 as a national meeting to be held every three years for Italian researchers in algorithms, data structures, complexity theory, and parallelanddistributedcomputing. Duetoasigni?cantparticipationofforeign researchers, starting from the second edition, CIAC evolved into an international conference. However,alltheeditionsofCIAChavebeenheldinRome. The proceedings of CIAC were published by World Scienti?c for the ?rst edition and by Springer-Verlag in the Lecture Notes in Computer Science series (volumes 778,1203and1767)forthesubsequenteditions. Aselectionofthepapersofthe fourth edition was published in a special issue of Theoretical Computer Science Vol. 285(1),2002. Thisyearweexpecttopublishanextendedversionofselected papers presented at the conference in a special issue of the journal Theory of Computing Systems.
In response to the call for papers for CIAC 2003, 57 papers were subm- ted, from which the Program Committee selected 23 papers for presentation at theconferencefrom18countries. Eachpaperwasevaluatedbyatleastthree Program Committee members with the help of 63 external reviewers. In addition to the selected papers, the Organizing Committee invited CharlesE. Leiserson(Cambridge),DavidPeleg(Rehovot),MichaelO. Rabin (CambridgeandJerusalem),JohnE. Savage(Providence),andLucaTrevisan (Berkeley)togiveplenarylecturesattheconference. Moreover,threetutorials byDavidPeleg,JaymeL. Szwarc?ter(RiodeJaneiro)andLucaTrevisanwere o?ered in the days preceding the conference. We wish to express our appreciation to all the authors of the submitted - pers, to the Program Committee members and the referees, to the Organizing Committee, and to the plenary and tutorial lecturers who accepted our in- tation.