Go to content Go to menu

Plenary Speakers

Alberto Marchetti-Spaccamela

Alberto Marchetti-Spaccamela is a professor of computer science at Sapienza University of Rome since 1991; in 1982-1983 he was a visiting scholar at UC Berkeley and in 1987-1991 he was a professor at the University of L’Aquila.

Alberto Marchetti-Spaccamela has authored more than 120 papers in journals and international conferences. His current research interests concern design and analysis of algorithms, and their applications.

He has co-authored a book “Approximation Algorithms” (Springer 1999) and four textbooks for University classes (in Italian). He has chaired International Conferences, Workshops and schools (WG 96, ICALP 97, WSDAAL 97, ICTCS 91, OLA 99, WAE 01, ATMOS 03, Hot TiNA 08, ICALP 09, TAPAS 11); he has been guest editor for special issues of Theoretical Computer Science, ACM Computing Surveys, Discrete Applied Mathematics, J. of Discrete Algorithms; he has co-edited five volumes published by Springer Verlag, and he has served in the program committee of more than fifty international conferences and workshops. He has served in the steering committee of ESA and is currently member of the WG and ATMOS steering committees.

He has been a member of the National Committee for the International Olympiads in Informatics and President of the Italian Chapter of the European Association for Theoretical Computer Science (EATCS).

Dániel Marx

Daniel Marx received his Ph.D. degree in Computer Science at Budapest University of Technology and Economics in 2005. Since that time he has held post-doc positions at various places, including Berlin, Budapest, and Tel Aviv. Currently he is enjoying a Humboldt Research Fellowship for Experienced Researchers at Humboldt-Universität zu Berlin. He is well known in the Theoretical Computer Science community as a problem solver with excellent algorithm and reduction designing skills. His main research areas include graph coloring, constraint satisfaction, approximability, discrete and computational geometry and others, mostly but not exclusively treated from the fixed parameter complexity point of view. He has publisehd over 60 research papers and gets his papers regularly accepted to leading broadly scoped computer science conferences such as SODA, ICALP, STOC or FOCS. He received the János Kemény prize awarded by the John von Neumann Computer Society in 2003 and the Gyula Farkas prize awarded by the János Bolyai Mathematical Society in 2004.

Invited Talks

  • Tuesday June 21, 9:00-10:00 – Alberto Marchetti-Spaccamela: Structures and Hyperstructures in Metabolic Networks
  • Thursday June 23, 9:00-10:00 – Dániel Marx: Important separators and parameterized algorithms

Alberto Marchetti-Spaccamela: Structures and Hyperstructures in Metabolic Networks

A large interest for metabolism in the computational biology community has lead to an avalanche of papers. Here we focus our attention on the study of metabolic networks that allow to represent cells of plants and animals as “chemical factories” where the various products are manufactured. The goal is to understand cell metabolism as the complete set of chemical reactions that occur in living cells, each reaction corresponding to the transformation of a set of one or more substances into another set.

Various models have been proposed to represent metabolic networks using graph and hypergraphs and many problems have been studied. We present two such problems that are challenging also for their computational aspects. The first one is the problem of characterizing metabolism in the network. Several approaches have been proposed many of which require finding suitably defined paths (and hyperpaths) in the network. We will discuss how finding and enumerating such paths is related to known graph problems while posing new algorithmic challenges.

The second problem deals with the use of graph theoretic measures in order to mine the structures of a metabolic networks and to provide further insight into its general characteristics. We will review known results based on measures such as degree distribution, centrality, diameter, clustering coefficients and so on and we will also discuss new approaches based on treewidth and Kelly width.

Dániel Marx: Important separators and parameterized algorithms

The notion of “important separators” and bounding the number of such separators turned out to be a very useful technique in the design of fixed-parameter tractable algorithms for multi(way) cut problems. For example, the recent breakthrough result of Chen et al. on the Directed Feedback Vertex Set problem can be also explained using this notion. In my talk, I will overview combinatorial and algorithmic results that can be obtained by studying such separators.