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.
Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs
Giuseppe F. Italiano
|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
|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
Physarum Can Compute Shortest Paths
|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: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
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.