Workshop GA - Graph algorithms and Applications

GA aims to provide a forum for researchers to discuss the most recent trends and results in graph algorithms and their applications. One goal is to show how theoretical advances, engineering principles and thorough experimental evaluations can help developers build efficient, robust, and scalable applications for domain-specific scenarios. Another goal is to extract, formalize, and model new algorithmic graph problems from modern real-world applications, exploring directions for future research.

The workshop is in honor of Giorgio Ausiello in the occasion of his 70th birthday.


09:00-09:05 Opening
09:05-10:00 Invited Lecture
Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs
Giuseppe F. Italiano
10:00-10:30 Coffee Break
10:30-10:50 Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon
David Eppstein, Michael Goodrich, Maarten Löffler, Darren Strash and Lowell Trott
10:50-11:10 Analysis of a Model for Social-Aware Forwarding Routing
Josep Diaz, Alberto Marchetti-Spaccamela, Dieter Mitsche, Paolo Santi and Julinda Stefa
11:10-11:30 Approximating Steiner Network Activation Problems
Zeev Nutov
11:30-11:40 Short Break
11:40-12:00 TSP on Cubic and Subcubic Graphs
Sylvia Boyd, Rene Sitters, Suzanne Van Der Ster and Leen Stougie
12:00-12:20 Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
Markus Bläser, Bodo Manthey and Raghavendra Rao B V
12:20-12:40 Reoptimization of Max k-Colorable Subgraph
Nicolas Boria
12:40-14:00 Lunch Break
14:00-15:00 Invited Lecture
Physarum Can Compute Shortest Paths
Kurt Mehlhorn
15:00-15:20 On the Approximability of Modularity Clustering
Bhaskar Dasgupta and Devendra Desai
15:20-15:40 Faster Algorithms for Rounding Fractional Spanning Trees
Vincenzo Bonifaci and Julian Mestre
15:40-16:00 On the Power of BFS for Computing the Diameter of Real-World Undirected Graphs
Pierluigi Crescenzi, Roberto Grossi, Michel Habib, Leonardo Lanzi and Andrea Marino
16:00-16:30 Coffee Break
16:30-16:50 Better Bounds for Incremental Frequency Allocation in Bipartite Graphs
Marek Chrobak, Łukasz Jeż and Jiří Sgall
16:50-17:10 On Relaxing the Constraints in Pairwise Compatibility Graphs
Tiziana Calamoneri, Rossella Petreschi and Blerina Sinaimeri
17:10-17:30 Telling Stories
Vicente Acuna, Etienne Birmele, Cottret Ludovic, Pierluigi Crescenzi, Jourdan Fabien, Vincent Lacroix, Alberto Marchetti-Spaccamela, Marino Andrea, Paulo Milreu, Marie-France Sagot and Leen Stougie
17:30-17:50 Exponential Approximation Schemata for some Network Design Problems
Nicolas Boria, Bourgeois Nicolas, Bruno Escoffier and Vangelis Paschos
17:50-18:10 The Strong Articulation Points of the Web Graph
Donatella Firmani and Luigi Laura


Submitted papers should consider any aspects of graph algorithms and their applications, including but not restricted to:

Sequential, parallel, randomized, parameterized, and distributed graph and network algorithms, I/O and cache-efficient graph algorithms, on-line and incremental graph algorithms, approximation algorithms for graph problems, game theoretical concepts, graph algorithms in computational geometry, graph algorithms in bioinformatics, graph drawing algorithms, graph models of the Web and social networks.

We are seeking for papers presenting theoretical results and/or computational studies. Position and survey papers as well as papers formalizing novel interesting open problems on the workshop topics are also welcome.


Authors are invited to submit an extended abstract or full paper of at most 12 pages and an optional appendix. Papers must be formatted in LaTeX. Contributions should be submitted electronically in pdf format via the EasyChair submission system, accessible at:

There will be no proceedings, but a selection of the papers accepted for presentation at the workshop will be invited for a special issue of Theoretical Computer Science. Indeed, because of the lack of a proceedings, submission of work that is intended for publication elsewhere is welcome. Such submissions should include details of the other submission.




Local Arrangements Committee (ICALP conference chairs)