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: http://www.easychair.org/conferences/?conf=ga20110
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.
