Curriculum Vitae di Luigi Laura Presentazione sinteticalaura/CV-LuigiLaura.pdf · 2015-11-02 ·...

Curriculum Vitae di Luigi Laura

Presentazione sintetica

Luigi Laura:

• si e laureato in ingegneria informatica ed ha conseguito il dottorato in ingegneria informaticaalla Sapienza.

• Ha conseguito l’abilitazione scientifica nazionale per le funzioni di professore universitario diseconda fascia (Professore Associato) nel settore concorsuale 9/H1 - Sistemi di Elaborazionedelle Informazioni e nel settore concorsuale 1/B1 - Informatica.

• Dal 1999 ha collaborato a vario titolo a diversi progetti di ricerca europei ed italiani.

• Dal 2002 a oggi ha insegnato:

– il corso di Fondamenti di Informatica alla Sapienza (corso di laurea in IngegneriaInformatica e, precedentemente, in Ingegneria Aerospaziale);

– il corso di Algoritmi e Strutture Dati alla Sapienza e a Tor Vergata (corso di laurea inIngegneria Informatica);

– il corso di Modelli e Complessita di Calcolo alla Sapienza (corso di laurea in IngegneriaInformatica);

– il corso integrativo di Information Systems alla Luiss (dipartimento di Economia eFinanza);

– il corso di Progetto di Sistemi Web Based a Tor Vergata (corso di laurea in LINFO).

• E cotitolare del brevetto: “Procedimento per il riconoscimento di autenticita di documenti etitoli di credito, in particolare banconote, e relativo sistema”.

• Dal 2006 e allenatore della squadra italiana per le Olimpiadi Internazionali di Informatica(IOI: International Olympiads in Informatics).

• Dal 2011 e responsabile scientifico delle Olimpiadi Italiane di Informatica, dai cui vincitorivengono poi selezionati i componenti della squadra italiana per le IOI.

• Collabora con diverse universita italiane e straniere e con il centro ricerca Google di NewYork.

• Dal 2000 e stato relatore di piu di un centinaio di tesi di laurea (triennale, magistrale e vecchioordinamento) alla Sapienza e a Tor Vergata.

• Svolge ricerca relativa ad algoritmi e�cienti, in particolare per grafi e dati di grandi dimen-sioni. E autore di 18 pubblicazioni su riviste internazionali e 47 pubblicazioni in conferenzeinternazionali.

• E coautore del testo Linguaggi, Modelli, Complessita (nuova edizione), Franco Angeli Editore2014.

• Dal 2012 fa parte del comitato editoriale del Journal of Discrete Mathematics (http://www.hindawi.com/journals/jdm/).

1

• Dal 2000 ha svolto attivita di revisione per lavori sottoposti ad alcune tra le principaliconferenze e riviste internazionali relative agli algoritmi.

• Esercita attivita professionale dal 2004.

Segue il Curriculum Vitae dettagliato nel formato dell’Allegato B del Decreto RettoraleUniversita di Roma “La Sapienza” n. 2474 del 07/08/2015.

2

LUIGI LAURACurriculum Vitae

Roma, 6 Ottobre 2015.

Part I – General Information

Full Name Luigi LauraDate of Birth November 10th, 1971Place of Birth Roma, ItaliaCitizenship ItalianPermanent Address Via Palestrina 5, 00189 Roma, Italia.Mobile Phone Number +39 335 7024555E-mail [email protected]

Spoken Languages Italian and English.

Part II – Education

Ph.D. in Engineering in Computer Science [Dottorato di Ricerca in IngegneriaInformatica]Sapienza Universita di Roma, Italy, 2003.Dissertation: Modeling and Mining Complex Information Systems.Advisor: Prof. Giorgio Ausiello, thesis committee: Prof. Stefano Leonardi, external reviewers:Prof. Ravi Kumar, Prof. Clyde Lee Giles.

Laurea degree in Engineering in Computer Science [Laurea in Ingegneria Informatica]Sapienza Universita di Roma, Italy, 1999.Dissertation: Risoluzione On-line di problemi Dial-a-ride.Advisor: Prof. Giorgio Ausiello, marks: 101/110.

Part III – Appointments

IIIA – Academic Appointments

Start End PositionAugust2013

July 2016 Research Fellow [titolare di assegno di ricerca], Sapienza Universita diRoma, Advisor Prof. Umberto Nanni. Research appointment: Siste-ma informativo a supporto dei sistemi di navigazione commerciale perpiccoli aerei operanti in aeroporti minori.

3

March 2013 May 2013 Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Paolo Franchin. Re-search appointment: Consulenza specialistica sulla realizzazione di unalgoritmo di costruzione automatica della rete Bayesiana del problemadella vulnerabilita sismica di un’infrastruttura spazialmente distribuita:a�namento e applicazione.

July 2012 November2012

Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Paolo Franchin. Researchappointment: Consulenza specialistica sulla realizzazione di un algorit-mo di costruzione automatica della rete Bayesiana del problema dellavulnerabilita sismica di un’infrastruttura spazialmente distribuita.

June 2011 September2011

Research Fellow [titolare di contratto di collaborazione alla ricerca], Sa-pienza Universita di Roma, Advisor Prof. Paolo Franchin. Research ap-pointment: Consulenza specialistica per lo sviluppo di algoritmi di ana-lisi di reti bayesiane all’interno di un codice di calcolo della vulnerabilitasismica di infrastrutture distribuite nello spazio; “parallelizzazione” ditale codice.

January2011

March 2011 Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Umberto Nanni. Researchappointment: Requisiti, analisi e progetto di un algoritmo per il VehicleRouting Problem con Time Windows (VRP-TW).

September2010

December2010

Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Progetto di algoritmi e di software per il calcolo di strongarticulation point e strong bridge per grafi di grandi dimensioni.

November2008

April 2009 Research Fellow [titolare di contratto di collaborazione alla ricerca], Sa-pienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Progetto e implementazione nel modello ‘external memo-ry’ di algoritmi basati su tecniche spettrali per matrici di grandi dimen-sioni con particolare riferimento all’uso delle tecniche di decomposizionematriciale SVD, CUR, CMD.

November2007

August2008

Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Progetto di algoritmi e di software per analizzare grandiquantita di dati, come grafi di grosse dimensioni (ad esempio campionidel WebGraph, che e il grafo i cui nodi sono le pagine (statiche) delWeb e i cui archi (diretti) sono i link tra di esse.

April 2006 August2006

Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Sperimentazione di algoritmi e di↵usione dei risultati delprogetto ALCOM-FT.

June 2005 November2005

Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Studio della complessita del calcolo di particolari equilibridi Nash.

4

December2004

March 2005 Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Implementazione di algoritmi per la misura di proprietaalgebriche di grafi.

January2004

October2004

Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Studio di modelli e algoritmi per il grafo del Web.

April 2003 December2003

Research Fellow [titolare di contratto di collaborazione alla ricerca],Sapienza Universita di Roma, Advisor Prof. Giorgio Ausiello. Researchappointment: Studio e implementazione di algoritmi per la gestione el’analisi di massive data set in memoria secondaria.

November2002

February2003

Research Fellow [titolare di contratto di collaborazione alla ricer-ca], Sapienza Universita di Roma, Advisor Prof. Alberto Marchetti-Spaccamela. Research appointment: Studio di modelli e e proprieta delWorld Wide Web (WWW) al fine di ottimizzare strumenti per l’accessoad essi basati su tecniche di Prefetching e Caching.

IIIB – Other Appointments

Start End PositionMarch 2015 July 2015 Member of the Commission of the Concorso per il reclutamento di 8

Tenenti in s.p. del Ruolo Tecnico Logistico dell’Arma dei CarabinieriAnno 2015, Decreto del Ministero della Difesa, Divisione Generale peril personale Militare, n. 38/1D del 5 Marzo 2015.

September2013

Current Appointed by the Direzione Generale Ordinamenti Scolastici, Ministerodell’Istruzione Universita e Ricerca, to organize an on-line course, CorsoOnline Competenze Digitali, for teachers of secondary schools (see PartXI for details).

May 2013 Current Member of the Comitato Olimpico per le Olimpiadi di Informatica Na-zionali ed Internazionali, Decreto del Ministero dell’Istruzione Univer-sita e Ricerca, Direzione Generale Ordinamenti Scolastici, Prot. n.0002289 del 6 Maggio 2013.

Part IV – Teaching experience

Main Lecturer (Professore a Contratto)

Year Institution Lecture/Course

2014/15 Corso di Laurea in Lingue per la Societa del-l’Informazione, Facolta di Lettere e Filosofia,Universita di Roma “Tor Vergata”

Progetto di Sistemi Web Based(corso curriculare)

Dipartimento di Economia e Finanza, dellaLibera Universita Internazionale degli StudiSociali (LUISS) “Guido Carli”

Information Systems(corso curriculare,contratto integrativo)

5















2008/09 Corso di Laurea in Ingegneria Informatica, Fa-colta di Ingegneria, Universita degli Studi diRoma “La Sapienza”

Modelli e Complessita di Calcolo(corso curriculare)

2007/08 Corso di Laurea in Ingegneria Informatica, Fa-colta di Ingegneria, Universita di Roma “TorVergata”

Algoritmi e Strutture Dati(corso curriculare)

Corso di Laurea in Ingegneria Informaticadell’Universita di Roma “La Sapienza”

Fondamenti di Informatica(corso curriculare)

2006/07 Corso di Laurea in Ingegneria Informatica, Fa-colta di Ingegneria, Universita di Roma “TorVergata”


Corso di Laurea in Ingegneria Informatica, Fa-colta di Ingegneria, Universita di Roma “LaSapienza”, polo didattico di Latina


6



Master di II livello in “Sistemi e Tecnologie ICTper la Sanita”, Facolta di Ingegneria, Universitadi Roma “Tor Vergata”


2005/06 Corso di Laurea in Ingegneria Informatica, Fa-colta di Ingegneria, Universita di Roma “LaSapienza”, polo didattico di Latina




2004/05 Corso di Laurea in Ingegneria Informaticadell’Universita di Roma “La Sapienza”


Corso di Laurea in Ingegneria Aerospaziale,Facolta di Ingegneria, Universita di Roma “LaSapienza”

Informatica(corso curriculare)

2003/04 Corso di Laurea in Ingegneria Informaticadell’Universita di Roma “La Sapienza”


Corso di Laurea in Ingegneria Aerospaziale,Facolta di Ingegneria, Universita di Roma “LaSapienza”


2002/03 Corso di Laurea in Ingegneria Aerospaziale,Facolta di Ingegneria, Universita di Roma “LaSapienza”


Teaching Assistant (Assistente/Tutor)

Year Institution Lecture/Course


Modelli e Complessita di Calcolo,docente: Prof. Giorgio Ausiello(corso curriculare)





7




Informatica Teorica, docente: Prof.Giorgio Ausiello (corso curriculare)


Informatica Teorica, docente: Prof.Giorgio Ausiello (corso curriculare)


Informatica,docente: Prof. Marco Cadoli(corso curriculare)


Informatica,docente: Prof. Marco Cadoli(corso curriculare)

Seminars

Year Seminar

2014/15 One seminar on Il mestiere dell’Informatico al tempo dei Big Data, Accademia deiLincei, Lezioni Lincee di Scienze Informatiche

2014/15 Two seminars on Big Data, Streaming Models and MapReduce, University of Verona,Course of Math Decisions, Prof. Romeo Rizzi

2014/15 Three seminars on 1) Hadoop 2) Web Maps, and 3) The WebGraph, University ofRoma Tor Vergata, Course of Algoritmi per il Web, Prof. Giuseppe F. Italiano



2011/12 Two seminars on MapReduce, Sapienza University of Roma, Course of Ingegneriadegli Algoritmi, Prof.ssa Irene Finocchi.

2011/12 Two seminars on MapReduce, Sapienza University of Roma, Course of Ingegneriadegli Algoritmi, Prof. Camil Demetrescu.

2007/08 One seminar on Storia della Calcolabilita, Sapienza University of Roma, Course ofStoria dell’Informatica, Prof. Giorgio Ausiello.



2005/06 Five seminars on Tecniche algoritmiche per il Web, Universita degli Studi dell’Aquila,Course of Algoritmi e Strutture Dati, Prof. Daniele Frigioni.

8

2002/03 One seminar on Models and Structure of the WebGraph. Ciclo di seminari “Algoritmia colazione”, University of Roma Tor Vergata.

Thesis Advisor (Relatore Tesi di Laurea e di Dottorato)

Since 2003 Luigi Laura has been the Thesis Advisor for students enrolled in the following courses:

• Laurea in Ingegneria Informatica (Vecchio Ordinamento, Triennale, Magistrale eSpecialistica), Sapienza Universita di Roma.

• Laurea in Lingue nella Societa dell’Informazione, Universita di Roma Tor Vergata.

Overall, Luigi Laura has been the Thesis Advisor for more than one hundred students in the abovementioned degrees.

Luigi Laura has also been in the Ph.D. Thesis committee of Luca Montanari, Ph.D. programin Computer Engineering, Sapienza Universita di Roma, XXV Cycle, 2012, Dissertation: OnlineFailure Prediction in Air Tra�c Control Systems.

Luigi Laura also collaborated in the Ph.D Thesis of Luca Allulli (Ph.D. program in ComputerEngineering, Sapienza Universita di Roma, XIX Cycle, 2006), Vincenzo Bonifaci (Ph.D. programin Computer Engineering, Sapienza Universita di Roma, XIX Cycle, 2006) , Donatella Firmani(Ph.D. program in Computer Engineering, Sapienza Universita di Roma, XXV Cycle, 2012) andFederico Santaroni (Ph.D. program in Computer Science and Control, Cycle XXVII, 2015).

Didactical Publications

In 2014 Luigi Laura co-authored, together with Giorgio Ausiello, Fabrizio d’Amore, and GiorgioGambosi, the book: Linguaggi Modelli Complessita, Franco Angeli Editore.

Luigi Laura also wrote lecture notes for students of the Informatica Teorica (and, later, Modelli eComplessita di Calcolo) courses: (together with Giorgio Ausiello) Brevissima introduzione al Lisp,and (together with Giorgio Ausiello and Giovanna Melideo )Complementi ed esercizi di InformaticaTeorica.

Part V - Society memberships

Luigi Laura is currently member of:

• European Association for Theoretical Computer Science (EATCS - https://www.eatcs.

org/), and its Italian Chapter (https://www.eatcs.org/index.php/italian-chapter).

• Associazione Italiana per il Calcolo Automatico (AICA - http://www.aicanet.it/).

Part VI - Participation in Research Projects

Luigi Laura is currently the leader of the Sapienza unit in the European Union fundedproject Profiling Relations In Drug tra�cking in Europe (PRIDE), grant procedure JU-ST/2014/JDRU/AG/DRUG. The goal of PRIDE project is to create a web-based system, accessibleby law enforcement Institutions/O�ces to improve actions against drugs tra�cking. This goal has

9

been inspired by the EU Action Plan on Drugs 2013-2016, in the field of drug supply reduction, tocontribute to a measurable reduction of the availability and supply of illicit drugs in the EU. Byusing a monitored website linked to the system, the project also aims at encouraging healthcareoperators to increase their knowledge on updated drug features for helping law enforcement.

Since 2000 Luigi Laura participated in the research unit of Dipartimento di Ingegneria InformaticaAutomatica e Gestionale (formerly Dipartimento di Informatica e Sistemistica), Sapienza Universitadi Roma, in the following research projects:

- MIUR PRIN 12 COFIN “AMANDA: Algorithmics for MAssive and Networked DAta”.

- MIUR PRIN 08 COFIN “Algorithmic Challenges for Data-intensive Processing on EmergingComputing Platforms (AlgoDEEP)”.

- MIUR PRIN 06 COFIN “Algorithms for Massive Information Structures and Data Streams(MAINSTREAM)”.

- MIUR PRIN 04 COFIN “Algorithms for the Next Generation Internet and Web (ALGO-NEXT)”.

- MIUR PRIN 02 COFIN “Algorithms for Internet and the Web (ALINWEB)”.

- MIUR PRIN 99 COFIN “Algorithms for Large Data Sets: Science and Engineering”.

- Progetto di ricerca Ateneo (ex quota 60%), research topic: modellizzazione edingegnerizzazione di algoritmi per reti.

- COevolution and Self-organization In dynamical Networks (COSIN), funded by the EU undercontract no. IST-2001-33555.

- Approximation and On-line Algorithms (APPOL II), funded by the EU under contract no.IST-2001-32007.

- Algorithmic Methods for Optimizing the Railways in Europe (AMORE), funded by the EUunder contract no. HPRN-CT-1999-00104.

- Algorithms and Complexity - Future Technologies (ALCOM-FT), funded by the EU undercontract no. IST-1999-14186.

- Algorithms and Complexity in Information Technology (ALCOM-IT), funded by the EUunder contract ESPRIT LTR no. 20244.

Part VII – Research Activities

The research activities of Luigi Laura are undoubtedly centered around graph algorithms, thatconstitute its main focus and are a key component in all the other areas described below, suchas the study of the WebGraph, that has also been the object of his PhD Dissertation, the on-line algorithms, also the object of his Master Thesis, the hypergraphs, and the computationalcomplexity results. In the following, in the cases in which the results appeared preliminarily in aconference and later in a journal, is cited only the journal. The citation numbers refer to the fulllist of publications of Luigi Laura, reported in Part XV.

10

Graph Algorithms

In [7] is studied the problem of computing articulation points and bridges in directed graphs; similarto the undirected case, a node is a strong articulation point of a strongly connected graph if thegraph is no longer strongly connected after its removal. In [4] has been presented an extensiveexperimental validation of these algorithms against large scale graphs. This result solved an openproblem posed by Beldiceanu et al. [CPAIOR 2005], and appeared almost 40 years later thanthe algorithm for the corresponding problem on undirected graphs. Later, building on this result,the problem of biconnected components has been studied: 2-Vertex Connectivity [28], 2-EdgeConnectivity [30], and an experimental evaluation of these results [29].

In a flow graph, i.e. a graph with a distinguished root vertex s that can reach all the other nodesin the graph, a vertex v is a dominator of vertex w if all the paths from s to w pass through v.In [4] it has been studied the problem of dominator certification, i.e. how to verify the correctnessof the solution reported by a dominator computing algorithm, and in [37] the related problem ofcomputing loop nesting forest, that represents a hierarchy of strongly connected subgraphs of agraph, has been faced. In [42] the problem of computing the dominators has been studied in thedynamic setting, i.e. when nodes and arcs are added or removed from the input graph. In [24]has been proposed a novel data structure, called the Depth First Tour Tree for the dynamic treeproblem, in which the goal is the maintenance of an arbitrary n-vertex forest, where the trees aresubject to joining and splitting by, respectively, adding and removing edges.

The problem of graph clustering has been considered in [6], where an evolutionary algorithmhas been proposed for tra�c networks, and in [68], where has been presented an algorithm forthe collaborative filtering, i.e. recommendation systems that are based on simultaneous clusteringsacross several categories and an overlap of interests in a bipartite graphs whose nodes are thecustomers and the items.

Graph algorithms have been proposed also in recent computational models (external memorymodel, streaming model, and MapReduce model) suited for massive scale graphs: for example, theDFS visit is the main ingredient of several graph algorithms but, if the graph cannot fit in mainmemory, and is thus stored in secondary memory, the DFS become the paradigmatic example ofwhat cannot be done in external memory. Many of the algorithms proposed for the WebGraph,discussed below, have been analyzed in the external memory model, and are either external orsemi-external : the main memory can store info about the nodes but not the edges. The othercomputational models are the streaming, in which the input, larger than the memory available,arrives as a stream of edges (and nodes), and the MapReduce, based on the MapReduce distributedcomputing framework proposed by Google and implemented in the open source Hadoop software.In the streaming model, in [51] has been proposed an algorithm to compute the strongly connectedcomponents of a directed graph, whilst in [8] all the biconnected properties (i.e. biconnected andconnected components, articulation points and bridges) of an undirected graph have been studied,with an experimental part focused on the Autonomous Systems network, that can be representedas a stream of BGP announcements. In [41] has been shown how to extend the ideas of [8] tocompute all the biconnected properties in the MapReduce framework.

Graph algorithms have been used also in the probabilistic inference in the physical simulationof interdependent critical infrastructure [34], and in the study of key nodes (i.e., players) in thecontext of Criminal Networks [31], highlighting structural di↵erences between criminal networksand other social networks.

11

WebGraph

After the seminal work of Kleinberg et al. in [COCOON 1999], The Web as a Graph: Measurements,Models, and Methods, there has been a lot of interest, in the literature, to the properties of theso-called WebGraph: the graph whose nodes are the static web pages and whose (directed) edgesare the hyperlink between them. This interest has been mainly due to the fact that the Google’sranking algorithm, PageRank, computes the ranks of web pages using only the graph structure ofthe web. Therefore, the WebGraph has been the object of a multi-faced research: samples werecollected and measured, showing peculiar properties such as powerlaws for indegree, outdegree andpagerank values distribution, the bow-tie shape, the presence of several communities, and a fractalstructure. At the same time, models were proposed, trying to capture these peculiarities, andalgorithms were developed, based on these properties, that allowed to measure larger samples, thusproviding a more accurate picture.

In this field, in [70] has been proposed a Multi-Layer Model, that describes the WebGraphas an ensemble of di↵erent regions generated by independent stochastic processes, in the spiritof the fractal properties observed by Dill et al. [VLDB 2001]. In [19] has been presented anexperimental study of WebGraph properties, based on a large crawl from 2001 of 200M pages andabout 1.4 billion edges made available by the WebBase project at Stanford. In [18] is presented acomparative analysis of several WebGraph models, whilst in [16] are discussed the the algorithmsdeveloped to compute these measures: a set of external and semi-external algorithms for computingproperties of massive graphs, and for the large scale simulation of stochastic graph models. Finally,in [15] is presented a complete picture of WebGraph properties, models and algorithms. Severalideas from the above described works have been recently used in the development of a search enginededicated to support law enforcements in the fight against illegal content in the TOR anonymousnetwork [3].

On-line algorithms

Vehicle Routing Problems are generalizations of the well known Traveling Salesman Problem; inseveral real world application, like a taxi service or packages delivery, requests are not known inadvance and arrive over time. These problems are called on-line problems and are often analyzed inthe framework of competitive analysis : the on-line solution is compared against the optimal o✏inesolution in which all the requests are known in advance; an on-line algorithm is competitive if theratio between its performance and the optimal o✏ine algorithm’s performance is bounded.

In this research area, the focus was on variations of the On-line Traveling Salesman Problem,studied in a seminal paper of Ausiello et al. [Algorithmica 2001]. In particular, in [17] has beenstudied the On-line Quota Traveling Salesman, where the goal of the traveling salesman is to reach agiven quota. In the On-line Price Collecting Traveling Salesman Problem, tackled in [12], each cityhas a given weight and penalty, and the goal is to collect a given quota of the weights of the citieswhile minimizing the length of the tour plus the penalties of the cities not in the tour. In [13] hasbeen studied the On-line Asymmetric Traveling Salesman Problem, i.e. the case when the distancefrom one point to another in a given space can be di↵erent from the inverse distance; this variationarises in many applications; for example, one can think of a delivery vehicle traveling throughone-way streets in a city, or of gasoline costs when traveling through mountain roads. In [11] hasbeen studied the improvement that can be achieved in terms of the competitive ratio if an on-linealgorithm is not only informed about the requests released so far, but also has a limited ability toforesee future requests; the findings are that the influence of lookahead can change considerablydepending on the particular objective function and metric space considered. In [71] is proposed, for

12

the On-Line Traveling Salesman Problem, a competitive algorithm for the case where the objectivefunction to minimize the maximum delay between the release time of a request and its serving time.

A di↵erent approach from competitive analysis has been used in the study of public transpor-tation networks [38]: in particular, in this work it has been measured empirically the quality of thesolutions o↵ered by timetabling routing in a real public transport network, where unpredictable de-lays may happen with a certain frequency, such as the public transport network of the metropolitanarea of Rome.

Computational Complexity

Computational complexity issues are present in several of the works discussed in this section; howe-ver, in the following works, the main result was the NP-hardness of distinct problems: the removalof Z-cycle from a Checkpoints and Communication Pattern [14], the computation of uniformly mi-xed Nash equilibria [10]. In particular, in [14], the absence of Z-cycle is a desirable property in adistributed computation since it guarantees that each checkpoint can be part of a global consistentcheckpoint. Unfortunately, minimizing the removal of Z-cycle is an NP-hard problem. An uniformequilibria is a Nash equilibria in which all the strategies played with nonzero probability, thus uni-form equilibria can be viewed as falling between pure and mixed Nash equilibria; playing a uniformstrategy is arguably the simplest way of mixing pure strategies but it is NP-hard to compute them[10].

Directed Hypergraphs

Directed hypergraphs are a generalization of directed graph. In the most general case, an hyperedgegoes from a source set of nodes to a target set of nodes, and the cost of hyperpaths can be measuredin various di↵erent ways, which have been used in a wide set of applications In [43] two hierarchiesare defined and then related: a hierarchy of classes of optimization problems based on the propertiesof the cost measures and a hierarchy based on the structure of the optimum hyperpaths. Thealgorithms to compute optimum hyperpaths under several cost measures are presented in [72].The underlying hypergraph structure is used to derive linear time algorithms to analyze propertiesof Conflict-Free and General Petri Nets in [9], and to model large scale repositories of LearningObjects [35].

Computer Supported Education

Some aspects of the didactical activities of Luigi Laura impacted also his research: the algorithmvisualization tool Leonardo Web [20] derived from teaching needs; the platform oii-web [27] hasbeen developed to support the training of the italian team for International Olympiads in Infor-matics (see Part XI for details); the visual tool, developed in [36] and based on dominator trees,will be used in the oii-web platform for personalized eLearning. Furthermore, the wiki-based plat-form for collaborative language learning, described in [26], has been developed in a joint projectwith English and Spanish teachers that won the “bando” Uncovering Excellence in Tor Vergatauniversity of Rome (2015).

Part VIII – Summary of Scientific Achievements

Luigi Laura, together with G. Crapanzano, S. Sassoli and A. Vitaletti, is the inventor of the italianpatent (brevetto) n. 0001343947: Procedimento per il riconoscimento di autenticita di documenti

13

e titoli di credito, in particolare banconote, e relativo sistema.

In Part XV is reported the full list of publications of Luigi Laura; below is reported an overview ofthe citation records, whilst updated citation records can be found in the following web pages:

• Scopus https://www.scopus.com/authid/detail.url?authorId=7801518841

• Google Scholar https://scholar.google.com/citations?user=6D332hgAAAAJ

Product type Number Data Base Start EndJournal Papers(International)

17 Scopus 2004 2015

Journal Papers(International)

18 Google Scholar 2004 2015

Conference Papers(International)

37 Scopus 2003 2015

Conference Papers(International)

47 Google Scholar 2002 2015

Books (teaching) 1 Google Scholar 2014 2014Italian Patents(Brevetti)

1 U�cio Italiano Brevetti e Marchihttp://www.uibm.gov.it/

2008 2008

Total Impact Factor1: 18,26.Scopus Google Scholar

Total Citations: 226 650Average Citations per Product: 226 / 54 = 4.19 650 / 65 = 10Hirsch (H) index: 8 13Normalized H index2: 8 / (2015-2003) = 8 / 12 = 0.67 13 / (2015-2002) = 13 /13 = 1

Part IX – Selected Publications

List of the publications selected for the evaluation. For each publication is reported authors,title, reference data, journal IF (if applicable), citations, press/media release (if any). The journalIF reported is from the journal’s home page or, if not available, from the website http://www.

scimagojr.com/. The citations reported, for both Google Scholar and Scopus, are in the formatX + Y , where X is the number of citations of the journal and Y is the number of citations of theconference version, if any.

1. D. Firmani, L. Georgiadis, G. F. Italiano, L. Laura, and F. Santaroni. Strong ArticulationPoints and Strong Bridges in Large Scale Graphs. Algorithmica, 2015; a preliminary versionappeared in [47]. DOI: http://dx.doi.org/10.1007/s00453-015-9991-z.IF: 0,791. Citations: Google Scholar = 0+14; Scopus = 0+4.

2. L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis. 2-Edge Connectivity in DirectedGraphs. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2015),

1Computed using 2014 Impact Factors from the journals’ home page or, when not available, from the website

http://www.scimagojr.com.

14

pp. 1988-2005, DOI: http://dx.doi.org/10.1137/1.9781611973730.132.IF: not a journal. Citations: Google Scholar = 6 ; Scopus = 1.

3. M. Naldi, S. Salcedo-Sanz, L. Carro-Calvo, L. Laura, A. Portilla-Figueras, G. F. Italia-no. A tra�c-based evolutionary algorithm for network clustering. Appl. Soft Comput.13(11): 4303-4319, 2013. DOI: http://dx.doi.org/10.1016/j.asoc.2013.06.022; preli-minary versions appeared in [51, 45].IF: 2,81. Citations: Google Scholar = 3+2 ; Scopus = 2+1.

4. L. Georgiadis, L. Laura, N. Parotsidis, R. E. Tarjan. Dominator Certification and Inde-pendent Spanning Trees: An Experimental Study. In Proceedings of the 12th InternationalSymposium on Experimental Algorithms (SEA 2013). DOI: http://dx.doi.org/10.1007/978-3-642-38527-8_26

IF: not a journal. Citations: Google Scholar = 9 ; Scopus = 1.

5. G. F. Italiano, L. Laura, and F. Santaroni. Finding Strong Bridges and Strong ArticulationPoints in Linear Time. Theoretical Computer Science 447: 74–84, 2012. DOI: http://dx.doi.org/10.1016/j.tcs.2011.11.011; a preliminary version appeared in [52].IF: 0,657. Citations: Google Scholar = 24+13 ; Scopus = 10+1.

6. G. Ausiello, D. Firmani, and L. Laura. Real-Time Monitoring of Undirected Networks:Articulation Points, Bridges, and Connected and Biconnected Components. Networks 59(3):275–288, 2012. DOI: http://dx.doi.org/10.1002/net.21450.IF: 0,83. Citations: Google Scholar = 4; Scopus = 4.

7. P. Alimonti, E. Feuerstein, L. Laura, and U. Nanni. Linear Time Analysis of Propertiesof Conflict-Free and General Petri nets. Theoretical Computer Science, 412(4-5): 320–338,2011; a preliminary version appeared in [73]. DOI: http://dx.doi.org/10.1016/j.tcs.2010.09.030.IF: 0,657. Citations: Google Scholar = 10; Scopus = 3.

8. V. Bonifaci, U. Di Iorio, and L. Laura. The complexity of uniformly mixed Nash equilibria.Theoretical Computer Science, 401(1-3): 144–152, 2008; preliminary versions of parts of thiswork appeared in [64, 59]. DOI: http://dx.doi.org/10.1016/j.tcs.2008.03.036.IF: 0,657. Citations: Google Scholar = 9+(9+3); Scopus = 5.

9. L. Allulli, G. Ausiello, V.Bonifaci, and L. Laura. On the Power of Lookahead in On-line ServerRouting Problems. Theoretical Computer Science, 408(2-3): 116–128, 2008; a preliminaryversion appeared in [62]. DOI: http://dx.doi.org/10.1016/j.tcs.2008.08.003.IF: 0,657. Citations: Google Scholar = 11+19 ; Scopus = 9+4.

10. G. Ausiello, V. Bonifaci, and L. Laura. The Online Prize-Collecting Traveling SalesmanProblem. Information Processing Letters, 107(6): 199–204, 2008. DOI: http://dx.doi.org/10.1016/j.ipl.2008.03.002.IF: 0,546. Citations: Google Scholar = 29 ; Scopus = 14.

11. G. Ausiello, V. Bonifaci, and L. Laura. The On-line Asymmetric Traveling Salesman Problem.Journal of Discrete Algorithms, 6(2): 290–298, 2008; a preliminary version appeared in [63].DOI: http://dx.doi.org/10.1016/j.jda.2007.03.002.IF: 0,75. Citations: Google Scholar = 14+12 ; Scopus = 8+3.

15

12. L. Allulli, R. Baldoni, L. Laura, and S. Tucci Piergiovanni. On the Complexity of RemovingZ-cycles from a Checkpoints and Communication Pattern. IEEE Transactions on Computers,56(2):853–858, 2007. DOI: http://dx.doi.org/10.1109/TC.2007.1044.IF: 1,659. Citations: Google Scholar = 3 ; Scopus = 1.

13. D. Donato, L. Laura, S. Leonardi, and S. Millozzi. The Web as a graph: how far we are.ACM Transactions on Internet Technologies, 7 (1), 2007. DOI: http://dx.doi.org/10.1145/1189740.1189744.IF: 0,769. Citations: Google Scholar = 48 ; Scopus = 21.

14. D. Donato, L. Laura, S. Leonardi, U. Meyer, S. Millozzi, and J. Sibeyn. Algorithms andExperiments for the Webgraph. Journal of Graph Algorithms and Applications, 10 (2), 2006;a preliminary version appeared in [69]. DOI: http://dx.doi.org/10.7155/jgaa.00125.IF: 1,14. Citations: Google Scholar = 14+34 ; Scopus = 8+2.

15. D. Donato, L. Laura, S. Leonardi, and S. Millozzi. Large scale properties of the webgraph.European Journal of Physics B, 38(2):239–243, 2004. DOI: http://dx.doi.org/10.1140/epjb/e2004-00056-6.IF: 1,345. Citations: Google Scholar = 100 ; Scopus = 56.

Part X – Abilitazione Scientifica Nazionale

December 2013 Abilitazione scientifica nazionale per le funzioni di professore universitario diseconda fascia (Professore Associato) nel settore concorsuale 9/H1 - Sistemi diElaborazione delle Informazioni.

January 2014 Abilitazione scientifica nazionale per le funzioni di professore universita-rio di seconda fascia (Professore Associato) nel settore concorsuale 1/B1 -Informatica.

Part XI – Olympiads in Informatics

Preliminaries

The International Olympiads in Informatics (IOI) are an annual programming competition forsecondary school students patronized by UNESCO. First IOI has been in Bulgaria in 1989. The 2014IOI, held in Taiwan, Taipei, saw participation by 84 countries and 311 contestants (each countrycan have up to four contestants). Participants are usually the winners of national competitions.

Italy participated in IOI for the first time in 2000, and since 2001 it started a national com-petition, promoted by a joint e↵ort of MIUR (Ministry of Education, University and Research)and AICA (Italian Association for Informatics and Automatic Calculus, a non-profit organization).The Italian Olympiads in Informatics (Olimpiadi Italiane di Informatica OII) are divided into threephases:

1. First Selection (Schools, November): in this phase, in their own schools, approximately20.000 students competes to solve, on paper, a test that involves math, logic, and program-ming abilities; in particular, there are some fragments of code (C/C++ or Pascal), and thestudents are asked to understand the behavior of the fragments.

2. Second Selection (Regions, April): in this phase there are approximately 40 venues,where approximately 1200 students, selected from the previous phase, compete by solving

16

three programming tasks on the computer. In this phase points are awarded for solving thetasks, independently from the complexity of the solution.

3. Third Selection (National Final, September): approximately 100 students are askedto solve e�ciently three programming tasks on the computer. They compete for 5 gold, 10silver and 20 bronze medals.

The top 20 students, i.e. gold and silver winners together with five distinguished bronze medalwinners, are selected as IOI candidates : they access (up to) four training camps of five days each,in which the candidates follow lessons and compete, until four of them are selected to representItaly at IOI competition.

In order to promote the Olympiads in Informatics, since 2013 the Direzione Generale per gliOrdinamenti Scolastici e la valutazione del sistema nazionale di istruzione del Ministero dell’Istru-zione, dell’Universita e della Ricerca (MIUR) promoted an online course for teachers of secondaryschools. This course, called Corso Online Competenze Digitali, is self-paced and its scope is to trainteachers in computer programming (in C/C++ and Pascal), algorithms and data structures, andprogramming contests. The aim is that trained teachers can, in turn, train their students. Teachersof secondary schools can freely register for this course. So far there have been three editions of thiscourse, with a fourth one scheduled to start in October 2015.

Appointments

All the following appointments have been jointly assigned to Luigi Laura by AICA and MIUR, theorganizers of the Italian Olympiads in Informatics.

Since 2006 Trainer for the IOI candidates: lectures on competitive programming algorithmsand data structures during the training camps.

Since 2011 Scientific advisor of the Italian Olympiads in Informatics: in particular thisactivity involves the supervision of the tests in the first selection, and the crea-tion of the programming tasks for both the second selection and the nationalfinal; the national final takes place every year in a di↵erent venue, and theappointment also includes the supervision of the network infrastructure of thefinal (approximately 100 computers including the two servers).

Since 2011 Coordinator of the IOI candidates selection process: this activity involves theschedule of the training camps and the coordination of all the trainers (teachers)and tutors (former IOI contestants).

Since 2013 Organizer of the Corso Online Competenze Digitali.Since 2013 Member of the Comitato Olimpico per le Olimpiadi di Informatica Nazionali ed

Internazionali.

Other activities related to the Olympiads in Informatics

Luigi Laura designed and supervised the development of a web based system, called oii-web wherethe students can train themselves for the programming contests. oii-web, based on the graderused in the International Olympiads in Informatics, is freely available as open source software andhas been used to implement three platforms so far:

OII-training is the platform devoted to the students that are interested in OII. In this platformthere are approximately 180 problems spanning several techniques and di�culties, ranging from

17

regional contests to IOI level. Furthermore, there are also the tests, from the first selection ofOII (schools selection), available as interactive online forms. This platform is considered in a betatesting phase, students are free to use it and, despite the lack of o�cial promotion so far (it is notlinked by the OII website) it has already approximately 500 users. This platform is available atthe url http://cms.di.unipi.it.

DIGIT is the platform used in the Corso Online Competenze Digitali. This platform is currentlythe richest of the three, in terms of contents and functionalities. There are video courses of C/C++and Pascal programming, Algorithms and Data structures, and some basic video tutorial as wellincluding how to use the platform to submit a solution. There are also some lecture notes, andall the material can be distributed to students as well; the video lectures are also available onthe OII channel on youtube. The MIUR used this platform, since October 2013, in three distinctcourses, with a fourth one scheduled to start in October 2015. So far approximately 2000 teachersfollowed this course, and the e↵ects on the OII were impressive: the participation of students inOII preliminary stages raised from 13k to 21k since the opening of these courses. This platform isavailable at the url http://cms.di.unipi.it/digit.

IOI-candidates is the last platform, and the only one not publicly available, since it is devotedto the IOI-candidates. This platform has been the original motivation to develop the whole oii-websystem. This platform has all the problems available to the other two platform, together with areserved set of problems to be used in the contests to rank the students. The students are askednot to discuss these problem in public forum or social network, since these are usually reused afterfew years.

Since 2014 Luigi Laura organizes, together with Giuseppe F. Italiano, the GATOR (Gara onlinedi Allenamento TOR vergata): an open online programming contest for the students to train forthe Second Selection of OII. More information can be found in the GATOR home page: http:

//www.disp.uniroma2.it/users/italiano/gator/.

Part XII – International collaborations

Except for the appointments presented in Part III, Luigi Laura have had/has active collaborationswith various researchers abroad. Some of the most noted are:

• Microsoft Research, India: Muthu Muthukrishan.

• University of Ioannina, Greece: Loukas Georgiadis.

• Facebook Core Data Science team, US: Smriti Bhagat.

• Warwick University, UK: Graham Cormode.

• Princeton University, US: Robert E. Tarjan.

• Kaiserslautern University, GE: Sven O. Krumke.

Part XIII - Other activities

Since 2012 Luigi Laura is in the editorial board of the Journal of Discrete Mathematics (http://www.hindawi.com/journals/jdm/).

18

In 2015 Luigi Laura has been the guest editor of the Special Issue on Visual Aspects in TechnologyEnhanced Learning, International Journal of Distance Education Technologies [21].

In 2011 Luigi Laura organized, together with Leonardo Querzoni, the first Workshop Workshop onAlgorithms and Model for Distributed Event Processing (AlMoDEP) [22].

In 2007 Luigi Laura edited, together with Giuseppe F. Italiano and Eugenio Moggi, the Proceedingsof the 10th Italian Conference on Theoretical Computer Science (ICTCS 2007) [23].

Luigi Laura has reviewed papers for the following journals: Algorithmica, Computing and Infor-matics, Discrete Mathematics, European Journal of Operational Research, Information ProcessingLetters, Journal of Combinatorial Optimization, Journal of Experimental Algorithmics, Networks,Theoretical Computer Science, Transportation Science.

Luigi Laura has reviewed papers for the following conferences: Algorithm Engineering and Experi-ments (ALENEX), European Symposium on Algorithms (ESA), International Colloquium on Au-tomata, Languages and Programming (ICALP), International Symposium on Algorithms and Com-putation (ISAAC), International Symposium on Mathematical Foundations of Computer Science(MFCS), International Symposium on Experimental Algorithms (SEA), ACM Symposium on Di-screte Algorithms (SODA), ACM Symposium on Parallel Algorithms and Architectures (SPAA),Workshop on Algorithms and Data Structure (WADS), Workshop on Approximation and OnlineAlgorithms (WAOA), International Workshop on Graph-Theoretic Concepts in Computer Science(WG), International World Wide Web Conference (WWW).

Part XIV - Talks in Conferences and Workshops

Invited talks:

• Dagstuhl, Germany, May 14th, 2014. Title: Shortest Hyperpaths. Dagstuhl Seminar 14201Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms andapplications. related formalisms and applications

• Tirana, Albania, September 27th, 2013. Title: Dealing with large and massive graphs, or: mygraph doesn’t fit in RAM!. Second International Symposium on Computing in Informaticsand Mathematics (ISCIM 2013).

• Shonan, Japan, January 9th, 2012. Title: Biconnected Components [and Articulation Pointsand Bridges] in MapReduce using Graph (Navigational) Sketches. Shonan Meeting Seminar11, Large-Scale Distributed Computation.

Conference talks:

• Sinaia, Romania, September 23rd, 2015. Presented the paper: V. Baraniello, C. Degano, L.Laura, M. Lozano Zahonero, M. Naldi, and S. Petroni. A Wiki-based approach to ComputerAssisted Translation for Collaborative Language Learning. Y. Li et al. (eds.),State-of-the-Art and Future Directions of Smart Learning, Lecture Notes in Educational Technology, pp.367-377, 2015. DOI: http://dx.doi.org/10.1007/978-981-287-868-7_45.

• Sinaia, Romania, September 23rd, 2015. Presented the paper: W. Di Luigi, G. Farina,L. Laura, U. Nanni, M. Temperini, and L. Versari. Three Uses of the Online Social Pro-gramming Training System: On Nature and Purpose of Spreading Algorithmic Problem Sol-ving. Y. Li et al. (eds.),State-of-the-Art and Future Directions of Smart Learning, Lecture

19

Notes in Educational Technology, pp. 385-395, 2015. DOI: http://dx.doi.org/10.1007/978-981-287-868-7_47.

• Barcelona, Spain, November 10th, 2014. Presented the paper: D. Firmani, G. F. Italiano, L.Laura The (not so) Critical Nodes of Criminal Networks. Proceedings of the First Workshopon Criminal Network Analysis and Mining (CRIMENET) 2014, SocInfo Workshop, pp.87-96,2014. DOI: http://dx.doi.org/10.1007/978-3-319-15168-7_12.

• Florence, Italy, September 9th, 2014. Presented the paper: P. Franchin, L. Laura. Proba-bilistic inference in the physical simulation of interdependent critical infrastructure systems.Proceedings of the SAFECOMP 2014 WORKSHOPS: ASCoMS, DECSoS, DEVVARTS, IS-SE, ReSA4CI, SASSUR, LNCS 8696, pp. 328-338, 2014. DOI: http://dx.doi.org/10.1007/978-3-319-10557-4_36.

• Tallin, Estonia, August 14th, 2014. Presented the paper: L. Laura, U. Nanni, and M. Tem-perini. The Organization of Large-Scale Repositories of Learning Objects with DirectedHypergraphs. Proceedings of the 7th International Workshop on Social and Personal Com-puting for Web-Supported Learning Communities (SPeL 2014), LNCS 8699, pp. 23-33, 2014.DOI: http://dx.doi.org/10.1007/978-3-319-13296-9_3.

• Tallin, Estonia, August 15th, 2014. Presented the paper: L. Laura, U. Nanni, and M. Tem-perini. Visual analysis based on dominator trees with application to personalized eLearning.Proceedings of the 13th International Conference on Web-based Learning (ICWL 2014), LNCS8613, pp. 207–212, 2014. DOI: http://dx.doi.org/10.1007/978-3-319-09635-3_23.

• Ljubljana, Slovenia. September 13th, 2012. Presented the paper: G. Ausiello, D. Firmani, L.Laura, and E. Paracone. Large-Scale Graph Biconnectivity in MapReduce. In Proceedingsof the Fourth Workshop on Massive Data Algorithmics (MASSIVE 2012).

• Ljubljana, Slovenia. September 13th, 2012. Presented the paper: L. Georgiadis, G. F.Italiano, L. Laura, and F. Santaroni. An Experimental Study of Dynamic Dominators. InProceedings of the 20th Annual European Symposium on Algorithms (ESA 2012), pp. 491-502.DOI: http://dx.doi.org/10.1007/978-3-642-33090-2_43.

• Limassol, Cyprus, August 28th, 2012. Presented the paper: S. Salcedo-Sanz, M. Naldi,L. Carro-Calvo, L. Laura, A. Portilla-Figueras, and G. F. Italiano. Tra�c vs Topology inNetwork Clustering: Does it Matter? In Proceedings of the Third International Workshopon TRa�c Analysis and Classification (TRAC 2012), pp. 36-41. DOI: http://dx.doi.org/10.1109/IWCMC.2012.6314174.

• Limassol, Cyprus, August 28th, 2012. Presented the paper: G. Ausiello, D. Firmani, and L.Laura. Real-time Analysis of Critical Nodes in Network Cores. In Proceedings of the ThirdInternational Workshop on TRa�c Analysis and Classification (TRAC 2012), pp. 42-46.DOI: http://dx.doi.org/10.1109/IWCMC.2012.6314175.

• Rome, Italy, April 20th, 2011. Presented the paper: L. Laura, and F. Santaroni. Com-puting Strongly Connected Components in the Streaming Model. In Proceedings of theFirst International ICST Conference (TAPAS’11), volume 6595 of Lecture Notes in Com-puter Science, pages 193–205. Springer-Verlag, 2011. DOI: http://dx.doi.org/10.1007/978-3-642-19754-3_20.

20

• Kona, Hawaii, USA, December 19th, 2010. Presented the paper: G. F. Italiano, L. Laura,and F. Santaroni. Finding Strong Bridges and Strong Articulation Points in Linear Time. InProceedings of the 4th Annual International Conference on Combinatorial Optimization andApplications (COCOA’10), pp.157-169. DOI: 10.1007/978-3-642-17458-2_14.

• Venice, Italy, May 24th, 2006. Presented the paper: V. Bonifaci, C. Demetrescu, I. Finocchi,and L. Laura. Visual Editing of Animated Algorithms: the Leonardo Web Builder. In Pro-ceedings of the International Working Conference on Advanced Visual Interfaces (AVI 2006),ACM Press 2006, pages 476–479. DOI: http://dx.doi.org/10.1145/1133265.1133362.

• New York, USA, November 20th, 2005. Presented the paper: V. Bonifaci, C. Demetrescu,I. Finocchi, G. F. Italiano, and L. Laura. Portraying algorithms with Leonardo Web. InProceedings of the WISE’05 International Workshop on Web-based Learning, New York City,USA, 2005, volume 3807 of Lecture Notes in Computer Science, pages 73–83. Springer-Verlag,2005. DOI: http://dx.doi.org/10.1007/11581116_8.

• Jeju island, Korea, August 18th, 2004. Presented the paper: G. Ausiello, M. Demange, L.Laura, and V. Paschos. Algorithms for the on-line quota traveling salesman problem. InProc. of 10th Annual International Computing and Combinatorics Conference (COCOON),volume 3106 of Lecture Notes in Computer Science, pages 290–299. Springer-Verlag, 2004.http://dx.doi.org/10.1007/978-3-540-27798-9_32.

• Isola d’Elba, Italy, May 28th, 2004. Presented the paper: G. Ausiello, V. Bonifaci, andL. Laura. On explorers, chasers and cameramen. In Paolo Ferragina and Roberto Grossi,editors, Proc. 3rd International Conference on Fun with Algorithms (FUN 2004), pages287–294, 2004.

• Isola d’Elba, Italy, May 27th, 2004. Presented the paper: D. Donato, L. Laura, and S.Millozzi. A beginner’s guide to the Webgraph: properties, models and algorithms. InPaolo Ferragina and Roberto Grossi, editors, Proc. 3rd International Conference on Fun withAlgorithms (FUN 2004), pages 295–306, 2004.

• Honolulu, Hawaii, USA, May 7th, 2002. Presented the paper: L. Laura, S. Leonardi, G.Caldarelli, and P. De Los Rios. A multi-layer model for the webgraph. In On-line proceedingsof the 2nd International Workshop on Web Dynamics., 2002. http://www.dcs.bbk.ac.uk/

webDyn2/onlineProceedings.html.

Part XV – Full Publication list in international journals andconference

Books

[1] G. Ausiello, F. d’Amore, G. Gambosi, and L. Laura. Linguaggi, Modelli, Complessita (nuovaedizione). Franco Angeli editore, 2014.

PhD Dissertation

[2] L. Laura. Modeling and Mining Complex Information Systems. Tesi di Dottorato, Facoltadi Ingegneria, Universita di Roma “La Sapienza”, 2003.

21

Journals

[3] L. Laura and G. Me. Searching the web for illegal content: the anatomy of a semantic searchengine. Journal of Soft Computing, to appear, 2015. DOI: 10.1007/s00500-015-1857-4

[4] D. Firmani, L. Georgiadis, G. F. Italiano, L. Laura, and F. Santaroni. Strong ArticulationPoints and Strong Bridges in Large Scale Graphs. Algorithmica, to appear, 2015. DOI:http://dx.doi.org/10.1007/s00453-015-9991-z

[5] C. Battista, A. Fumi, L. Laura, M.M. Schiraldi. Multiproduct slot allocation heuristic tominimize storage space. International Journal of Retail & Distribution Management, Vol. 42Iss: 3, pp.172 - 186, 2014. DOI: http://dx.doi.org/10.1108/IJRDM-03-2012-0024

[6] M. Naldi, S. Salcedo-Sanz, L. Carro-Calvo, L. Laura, A. Portilla-Figueras, G. F. Italiano.A tra�c-based evolutionary algorithm for network clustering. Appl. Soft Comput. 13(11):4303-4319, 2013. DOI: http://dx.doi.org/10.1016/j.asoc.2013.06.022

[7] G. F. Italiano, L. Laura, and F. Santaroni. Finding Strong Bridges and Strong ArticulationPoints in Linear Time. Theoretical Computer Science 447: 74–84, 2012. DOI: http://dx.doi.org/10.1016/j.tcs.2011.11.011

[8] G. Ausiello, D. Firmani, and L. Laura. Real-Time Monitoring of Undirected Networks:Articulation Points, Bridges, and Connected and Biconnected Components. Networks 59(3):275–288, 2012. DOI: http://dx.doi.org/10.1002/net.21450

[9] P. Alimonti, E. Feuerstein, L. Laura, and U. Nanni. Linear Time Analysis of Propertiesof Conflict-Free and General Petri nets. Theoretical Computer Science, 412(4-5): 320–338,2011; una versione preliminare e apparsa in [73].

[10] V. Bonifaci, U. Di Iorio, and L. Laura. The complexity of uniformly mixed Nash equilibria.Theoretical Computer Science, 401(1-3): 144–152, 2008; versioni preliminari sono apparse in[64, 59].

[11] L. Allulli, G. Ausiello, V.Bonifaci, and L. Laura. On the Power of Lookahead in On-line ServerRouting Problems. Theoretical Computer Science, 408(2-3): 116–128, 2008; una versionepreliminare e apparsa in [62].

[12] G. Ausiello, V. Bonifaci, and L. Laura. The Online Prize-Collecting Traveling SalesmanProblem. Information Processing Letters, 107(6): 199–204, 2008.

[13] G. Ausiello, V. Bonifaci, and L. Laura. The On-line Asymmetric Traveling Salesman Problem.Journal of Discrete Algorithms, 6(2): 290–298, 2008; una versione preliminare e apparsa in[63].

[14] L. Allulli, R. Baldoni, L. Laura, and S. Tucci Piergiovanni. On the Complexity of RemovingZ-cycles from a Checkpoints and Communication Pattern. IEEE Transactions on Computers,56(2):853–858, 2007.

[15] D. Donato, L. Laura, S. Leonardi, and S. Millozzi. The Web as a graph: how far we are.ACM Transactions on Internet Technologies, 7 (1), 2007.

[16] D. Donato, L. Laura, S. Leonardi, U. Meyer, S. Millozzi, and J. Sibeyn. Algorithms andExperiments for the Webgraph. Journal of Graph Algorithms and Applications, 10 (2), 2006;una versione preliminare e apparsa in [69].

22

[17] G. Ausiello, M. Demange, L. Laura, and V. T. Paschos. Algorithms for the on-line quotatraveling salesman problem. Inf. Process. Lett., 92(2):89–94, 2004; una versione preliminaree apparsa in [65].

[18] D. Donato, L. Laura, S. Leonardi, and S. Millozzi. Simulating the webgraph: A comparativeanalysis of models. Computing in Science and Engineering, 6(6):84–89, 2004.

[19] D. Donato, L. Laura, S. Leonardi, and S. Millozzi. Large scale properties of the webgraph.European Journal of Physics B, 38(2):239–243, 2004.

[20] V. Bonifaci, C. Demetrescu, I. Finocchi, and L. Laura. A java-based system for buildinganimated presentations over the web. Science of Computer Programming, 53(1):37–49, 2004.

Volume Editor

[21] L. Laura, U. Nanni, and M. Temperini (editors). Special Issue on Visual Aspects in TechnologyEnhanced Learning. International Journal of Distance Education Technologies, to appear.

[22] L. Laura and L. Querzoni (editors). Proceedings of the first Workshop on Algorithmsand Model for Distributed Event Processing (AlMoDEP). ACM International ConferenceProceedings Series, 2011.

[23] G.F. Italiano, E. Moggi, and L. Laura (editors). Proceedings of the 10th Italian Conferenceon Theoretical Computer Science (ICTCS 2007). World Scientific, 2007.

Conferences

[24] G. Farina and L. Laura. Dynamic subtrees queries revisited: the Depth First Tour Tree. Toappear in the Proceedings of the 26th International Workshop on Combinatorial Algorithms(IWOCA).

[25] L. Laura and G. Me. Searching the web for illegal content: the anatomy of a semanticsearch engine. Proceedings of the 10th International Conference on Global Security, Safetyand Sustainability, (ICGS3 2015), pp. 113-122. DOI: 10.1007/978-3-319-23276-8_10.

[26] V. Baraniello, C. Degano, L. Laura, M. Lozano Zahonero, M. Naldi, and S. Petroni. AWiki-based approach to Computer Assisted Translation for Collaborative Language Lear-ning. Y. Li et al. (eds.),State-of-the-Art and Future Directions of Smart Learning, LectureNotes in Educational Technology, pp. 367-377, 2015. DOI: http://dx.doi.org/10.1007/978-981-287-868-7_45.

[27] W. Di Luigi, G. Farina, L. Laura, U. Nanni, M. Temperini, and L. Versari. Three Usesof the Online Social Programming Training System: On Nature and Purpose of SpreadingAlgorithmic Problem Solving. Y. Li et al. (eds.),State-of-the-Art and Future Directions ofSmart Learning, Lecture Notes in Educational Technology, pp. 385-395, 2015. DOI: http://dx.doi.org/10.1007/978-981-287-868-7_47.

[28] L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis. 2-Vertex Connectivity in Di-rected Graphs. Proceedings of the Automata, Languages, and Programming - 42nd In-ternational Colloquium, (ICALP 2015), pp. 605-616, DOI: http://dx.doi.org/10.1007/978-3-662-47672-7_49.

23

[29] W. Di Luigi, L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis. 2-Connectivity in DirectedGraphs: An Experimental Study. Proceedings of the Seventeenth Workshop on AlgorithmEngineering and Experiments (ALENEX 2015), pp. 173-187, DOI: http://dx.doi.org/10.1137/1.9781611973754.15.

[30] L. Georgiadis, G. F. Italiano, L. Laura, N. Parotsidis. 2-Edge Connectivity in DirectedGraphs. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2015),pp. 1988-2005, DOI: http://dx.doi.org/10.1137/1.9781611973730.132.

[31] D. Firmani, G. F. Italiano, L. Laura The (not so) Critical Nodes of Criminal Net-works. Proceedings of the First Workshop on Criminal Network Analysis and Mining (CRI-MENET) 2014, SocInfo Workshop, pp.87-96, 2014. DOI: http://dx.doi.org/10.1007/

978-3-319-15168-7_12.

[32] L. Laura, G. Me, B. D’Alessio , A. Capone, M. Mignone. Vertical semantic discovery:the SICH approach on NPS Proceedings of the 6th International Conference on IntelligentNetworking and Collaborative Systems (INCoS 2014), ISBN 978-1-4799-6386-7, pp. 119-124.

[33] F. d’Amore, L. Laura. eGovernment Interventions: The Multiple Projects EvaluationProblem. ICETE 2012, CCIS 455, pp. 88–100, 2014.. DOI:10.1007/978-3-662-44791-8 6.

[34] P. Franchin, L. Laura. Probabilistic inference in the physical simulation of interdependent cri-tical infrastructure systems. Proceedings of the SAFECOMP 2014 WORKSHOPS: ASCoMS,DECSoS, DEVVARTS, ISSE, ReSA4CI, SASSUR, LNCS 8696, pp. 328-338, 2014. DOI:http://dx.doi.org/10.1007/978-3-319-10557-4_36.

[35] L. Laura, U. Nanni, and M. Temperini. The Organization of Large-Scale Repositories ofLearning Objects with Directed Hypergraphs. Proceedings of the 7th International Workshopon Social and Personal Computing for Web-Supported Learning Communities (SPeL 2014),LNCS 8699, pp. 23-33, 2014. DOI: http://dx.doi.org/10.1007/978-3-319-13296-9_3.

[36] L. Laura, U. Nanni, and M. Temperini. Visual analysis based on dominator trees withapplication to personalized eLearning. Proceedings of the 13th International Conference onWeb-based Learning (ICWL 2014), LNCS 8613, pp. 207–212, 2014. DOI: http://dx.doi.org/10.1007/978-3-319-09635-3_23.

[37] L. Georgiadis, L. Laura, N. Parotsidis, R. E. Tarjan. Loop Nesting Forests, Dominators, andApplications. Proceedings of the 13th International Symposium on Experimental Algorithms(SEA 2014), LNCS 8504, pp. 174-186, 2014.

[38] D. Firmani, G. F. Italiano, L. Laura, and F. Santaroni. Is Timetabling Routing AlwaysReliable for Public Transport? Proceedings of the 13th Workshop on Algorithmic Approachesfor Transportation Modelling, Optimization, and Systems (ATMOS 2013). DOI: http://dx.doi.org/10.4230/OASIcs.ATMOS.2013.15

[39] G. Ausiello, D. Firmani, and L. Laura. The (Betweenness) Centrality of Critical Nodes andNetwork Cores. In Proceedings of the Fourth International Workshop on TRa�c Analysisand Classification (TRAC 2013). DOI: http://dx.doi.org/10.1109/IWCMC.2013.6583540

[40] L. Georgiadis, L. Laura, N. Parotsidis, R. E. Tarjan. Dominator Certification and Inde-pendent Spanning Trees: An Experimental Study. In Proceedings of the 12th InternationalSymposium on Experimental Algorithms (SEA 2013). DOI: http://dx.doi.org/10.1007/978-3-642-38527-8_26

24

[41] G. Ausiello, D. Firmani, L. Laura, and E. Paracone. Large-Scale Graph Biconnectivity in Ma-pReduce. In Proceedings of the Fourth Workshop on Massive Data Algorithmics (MASSIVE2012).

[42] L. Georgiadis, G. F. Italiano, L. Laura, and F. Santaroni. An Experimental Study of DynamicDominators. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA2012), pp. 491-502. DOI: http://dx.doi.org/10.1007/978-3-642-33090-2_43.

[43] G. Ausiello, G. F. Italiano, L. Laura, U. Nanni, and F. Sarracco. Structure Theoremsfor Optimum Hyperpaths in Directed Hypergraphs. In Proceedings of Second InternationalSymposium of Combinatorial Optimization (ISCO 2012).

[44] F. d’Amore, L. Laura, L. Luciani, and F. Pagliarini. Planning, Designing, and EvaluatingMultiple eGovernment Interventions. In Proceedings of the International Conference on e-Business (ICE-B 2012).

[45] S. Salcedo-Sanz, M. Naldi, L. Carro-Calvo, L. Laura, A. Portilla-Figueras, and G. F. Italiano.Tra�c vs Topology in Network Clustering: Does it Matter? In Proceedings of the ThirdInternational Workshop on TRa�c Analysis and Classification (TRAC 2012), pp. 36-41.DOI: http://dx.doi.org/10.1109/IWCMC.2012.6314174.

[46] G. Ausiello, D. Firmani, and L. Laura. Real-time Analysis of Critical Nodes in Network Cores.In Proceedings of the Third International Workshop on TRa�c Analysis and Classification(TRAC 2012), pp. 42-46. DOI: http://dx.doi.org/10.1109/IWCMC.2012.6314175.

[47] D. Firmani, G. F. Italiano, L. Laura, A. Orlandi and F. Santaroni. Computing StrongArticulation Points and Strong Bridges in Large Scale Graphs. In Proceedings of the 11thInternational Symposium on Experimental Algorithms (SEA 2012).

[48] R. Beretta and L. Laura. Performance Evaluation of Algorithms for Newspaper ArticleIdentification. In Proceedings of the Eleventh International Conference on Document Analysisand Recognition (ICDAR 2011).

[49] S. Salcedo-Sanz, M. Naldi, L. Carro-Calvo, L. Laura, A. Portilla-Figueras, and G. F. Italiano.An Evolutionary Algorithm for Network Clustering through Tra�c Matrices. In Proceedingsof the Second International Workshop on TRa�c Analysis and Classification (TRAC 2011).

[50] G. Ausiello, D. Firmani, and L. Laura. Real-time Anomalies Detection and Analysis ofNetwork Structure, with application to the Autonomous System Network. In Proceedings ofthe Second International Workshop on TRa�c Analysis and Classification (TRAC 2011).

[51] L. Laura, and F. Santaroni. Computing Strongly Connected Components in the StreamingModel. In Proceedings of the First International ICST Conference (TAPAS’11), volume6595 of Lecture Notes in Computer Science, pages 193–205. Springer-Verlag, 2011. DOI:http://dx.doi.org/10.1007/978-3-642-19754-3_20.

[52] G. F. Italiano, L. Laura, and F. Santaroni. Finding Strong Bridges and Strong Arti-culation Points in Linear Time. In Proceedings of the 4th Annual International Con-ference on Combinatorial Optimization and Applications (COCOA’10), pp.157-169. DOI:10.1007/978-3-642-17458-2_14.

[53] L. Laura, M. Naldi, and G. F. Italiano. Tra�c-based Network Clustering. In Proceedings ofthe First International Workshop on TRa�c Analysis and Classification (TRAC 2010).

25

[54] F.Dellutri, L. Laura, V. Ottaviani, and G. F. Italiano. Extracting Social Networks fromseized Smartphone and Web data. In Proceedings of the First IEEE International Workshopon Information Forensics and Security (WIFS 2009).

[55] T. Di Mascio, L. Laura, and V. Mirabella. The interface of VISTO: a new Vector Image SearchTOol. In Proceedings of the 12th International Conference on Human-Computer Interaction(HCI 2007).

[56] L. Allulli, G. Ausiello, V.Bonifaci, and L. Laura. On-line Algorithms, Real Time, the Virtueof Laziness, and the Power of Clairvoyance. In Proceedings of the 3rd Annual Conferenceon Theory and Applications of Models of Computation (TAMC06), volume 3959 of LectureNotes in Computer Science, pages 1–20. Springer-Verlag, 2006.

[57] G. Ausiello and L. Laura. Algorithmic research for the 21st century. Shangai Forum 2005http://www.shanghaiforum.org.cn, in Shangai Forum Antology, Fudan University press,pages 31–50.

[58] V. Bonifaci, C. Demetrescu, I. Finocchi, and L. Laura. Visual Editing of Animated Al-gorithms: the Leonardo Web Builder. In Proceedings of the International Working Con-ference on Advanced Visual Interfaces (AVI 2006), ACM Press 2006, pages 476–479. DOI:http://dx.doi.org/10.1145/1133265.1133362.

[59] V. Bonifaci, U. Di Iorio, and L. Laura. New results on the complexity of uniformly mixed Nashequilibria. In Proceedings of the 1st Workshop on Internet and Network Economics (WINE2005), volume 3828 of Lecture Notes in Computer Science, pages 1023–1032. Springer-Verlag,2005.

[60] V. Bonifaci, C. Demetrescu, I. Finocchi, G. F. Italiano, and L. Laura. Portraying algorithmswith Leonardo Web. In Proceedings of the WISE’05 International Workshop on Web-basedLearning, New York City, USA, 2005, volume 3807 of Lecture Notes in Computer Science,pages 73–83. Springer-Verlag, 2005. DOI: http://dx.doi.org/10.1007/11581116_8.

[61] L. Laura, U. Nanni, and F. Sarracco. Fast LSI-based Techniques for Query Expansion in TextRetrieval Systems. In Proc. of 2nd Workshop on Text-based Information Retrieval (TIR-05),pp. 15-28.

[62] L. Allulli, G. Ausiello, and L. Laura. On the power of lookahead in on-line vehicle routingproblems. In Proc. of 10th Annual International Computing and Combinatorics Conference(COCOON), volume 3595 of Lecture Notes in Computer Science, pages 728–736. Springer-Verlag, 2005.

[63] G. Ausiello, V. Bonifaci, and L. Laura. The on-line asymmetric traveling salesman problem. InProc. 9th International Workshop on Algorithms and Data Structures (WADS 2005), volume3608 of Lecture Notes in Computer Science, pages 306–317. Springer-Verlag, 2005.

[64] V. Bonifaci, U. Di Iorio, and L. Laura. On the complexity of uniformly mixed Nash equili-bria and related regular subgraph problems. In Proc. of the 15th International Symposiumon Fundamentals of Computation Theory (FCT) 2005 , volume 3623 of Lecture Notes inComputer Science, pages 197–206. Springer-Verlag, 2005.

[65] G. Ausiello, M. Demange, L. Laura, and V. Paschos. Algorithms for the on-line quota trave-ling salesman problem. In Proc. of 10th Annual International Computing and Combinatorics

26

Conference (COCOON), volume 3106 of Lecture Notes in Computer Science, pages 290–299.Springer-Verlag, 2004.

[66] G. Ausiello, V. Bonifaci, and L. Laura. On explorers, chasers and cameramen. In Paolo Ferra-gina and Roberto Grossi, editors, Proc. 3rd International Conference on Fun with Algorithms(FUN 2004), pages 287–294, 2004.

[67] D. Donato, L. Laura, and S. Millozzi. A beginner’s guide to the Webgraph: properties, modelsand algorithms. In Paolo Ferragina and Roberto Grossi, editors, Proc. 3rd InternationalConference on Fun with Algorithms (FUN 2004), pages 295–306, 2004.

[68] D. Dubashi, L. Laura, and A. Panconesi. Analysis and experimental evaluation of a simplealgorithm for collaborative filtering in the planted partition model. In Proc. of 23rd conferenceon Foundations Of Software Technology And Theoretical Computer Science (FSTTCS ’03).,volume 2914 of Lecture Notes in Computer Science, pages 168–182. Springer-Verlag, 2003.

[69] L. Laura, S. Leonardi, S. Millozzi, U. Meyer, and J.F. Sibeyn. Algorithms and Experimentsfor the Webgraph. In Proc. of the 11th Annual European Symposium on Algorithms (ESA),volume 2832 of Lecture Notes in Computer Science, pages 703–714. Springer-Verlag, 2003.

[70] L. Laura, S. Leonardi, G. Caldarelli, and P. De Los Rios. A multi-layer model for thewebgraph. In On-line proceedings of the 2nd International Workshop on Web Dynamics.,2002. http://www.dcs.bbk.ac.uk/webDyn2/onlineProceedings.html.

[71] M. Lipmann, L. Laura, A. Marchetti-Spaccamela, S.O. Krumke, W.E. de Paepe, D. Poen-sgen, and L. Stougie. Non-abusiveness helps: An o(1)-competitive algorithm for minimizingthe maximum flow time in the online traveling salesman problem. In Proceedings of the5th International Workshop on Approximation Algorithms for Combinatorial Optimization,volume 2462 of Lecture Notes in Computer Science, pages 200–214. Springer-Verlag, 2002.

Technical Reports

[72] G. Ausiello, G.F. Italiano, L. Laura, U. Nanni and F. Sarracco. Classification and Traver-sal Algorithmic Techniques for Optimization Problems on Directed Hyperpaths. TechnicalReport TR-18-10, Department of Computer and System Sciences, Universita di Roma LaSapienza, Roma, Italy, 2010.

[73] P. Alimonti, E. Feuerstein, L. Laura, and U. Nanni. Linear Time Analysis of Properties ofConflict-Free and General Petri nets. Technical Report TR-09-10, Department of Computerand System Sciences, Universita di Roma La Sapienza, Roma, Italy, 2010.

[74] G. Ausiello, L. Laura, and E. Pini. A diligent algorithm for OL-TRP on the line. TechnicalReport TR-03-06, Department of Computer and System Sciences, Universita di Roma LaSapienza, Roma, Italy, 2006.

[75] D. Donato, L. Laura, S. Leonardi, and S. Millozzi. A software library for generating andmeasuring massive webgraphs. Technical Report D13, COSIN European Research Project,2004.

[76] T. Buhnik, L. Laura, and S. Leonardi. A phenomenological analysis of the p2p networksbased on gnutella protocol. Technical Report TR-03-03, Department of Computer and SystemSciences, Universita di Roma La Sapienza, Roma, Italy, 2003.

27

Manuscripts

[77] G. Ausiello, L. Laura e G. Melideo. Complementi ed esercizi di Informatica Teorica.

[78] G. Ausiello e L. Laura. Brevissima introduzione al Lisp.

[79] L. Laura. Risoluzione On-line di problemi Dial-a-ride. Tesi di Laurea, Facolta di Ingegneria,Univesita di Roma “La Sapienza, Ottobre 1999.

Dichiarazione sostitutiva di certificazione

DICHIARAZIONI SOSTITUTIVE DI CERTIFICAZIONI(art. 46, comma 1 del D.P.R. n.445/2000)DICHIARAZIONI SOSTITUTIVE DELL’ATTO DI NOTORIETA(art. 47 , comma 1 del D.P.R. n.445/2000)

Il sottoscritto Luigi Laura, codice fiscale LRALGU71S10H501Q, nato a Roma il 10 Novembre1971, di sesso maschile, attualmente residente a Roma, Via Palestrina 5 cap 00189, telefono06/30366161 consapevole che le dichiarazioni mendaci sono punite ai sensi del Codice penale edelle leggi speciali in materia

DICHIARA:

• di essere in possesso dei titoli e delle pubblicazioni riportate nell’allegato Curriculum Vitae;

• che ogni contenuto relativo a titoli, pubblicazioni e attivita svolte nel CV allegato e conformeal vero.

Roma, 6 Ottobre 2015,

Il DichiaranteAutorizzo il trattamento dei dati personali contenuti nel mio Curriculum Vitae ai sensi dell’art. 13del D.L. 196/2003 e successive modificazioni.

Luigi Laura

28

Curriculum Vitae di Luigi Laura Presentazione sinteticalaura/CV-LuigiLaura.pdf · 2015-11-02 ·...

Documents

Transcript of Curriculum Vitae di Luigi Laura Presentazione sinteticalaura/CV-LuigiLaura.pdf · 2015-11-02 ·...