# 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.

## PROGRAM

09:00-09:05 |
Opening |
||

09:05-10:00 |
Invited LectureImproved 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 PhenomenonDavid Eppstein, Michael Goodrich, Maarten Löffler, Darren Strash and Lowell Trott |
||

10:50-11:10 |
Analysis of a Model for Social-Aware Forwarding RoutingJosep Diaz, Alberto Marchetti-Spaccamela, Dieter Mitsche, Paolo Santi and Julinda Stefa |
||

11:10-11:30 |
Approximating Steiner Network Activation ProblemsZeev Nutov |
||

11:30-11:40 |
Short Break |
||

11:40-12:00 |
TSP on Cubic and Subcubic GraphsSylvia Boyd, Rene Sitters, Suzanne Van Der Ster and Leen Stougie |
||

12:00-12:20 |
Smoothed Analysis of Partitioning Algorithms for Euclidean FunctionalsMarkus Bläser, Bodo Manthey and Raghavendra Rao B V |
||

12:20-12:40 |
Reoptimization of Max k-Colorable SubgraphNicolas Boria |
||

12:40-14:00 |
Lunch Break |
||

14:00-15:00 |
Invited LecturePhysarum Can Compute Shortest Paths Kurt Mehlhorn |
||

15:00-15:20 |
On the Approximability of Modularity ClusteringBhaskar Dasgupta and Devendra Desai |
||

15:20-15:40 |
Faster Algorithms for Rounding Fractional Spanning TreesVincenzo Bonifaci and Julian Mestre |
||

15:40-16:00 |
On the Power of BFS for Computing the Diameter of Real-World Undirected GraphsPierluigi 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 GraphsMarek Chrobak, Łukasz Jeż and Jiří Sgall |
||

16:50-17:10 |
On Relaxing the Constraints in Pairwise Compatibility GraphsTiziana Calamoneri, Rossella Petreschi and Blerina Sinaimeri |
||

17:10-17:30 |
Telling StoriesVicente 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 ProblemsNicolas Boria, Bourgeois Nicolas, Bruno Escoffier and Vangelis Paschos |
||

17:50-18:10 |
The Strong Articulation Points of the Web GraphDonatella Firmani and Luigi Laura |

## SCOPE

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.

## SUBMISSION GUIDELINES

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.

## IMPORTANT DATES

- Submission deadline: Wednesday, May 4, 2011
- Notification: Friday, May 20, 2011
- Workshop: Sunday July 3rd, 2011 (ETH Zurich, Switzerland)

## PLENARY SPEAKERS

- Giuseppe F. Italiano, U. Rome "Tor Vergata"
- Kurt Mehlhorn, MPII, Saarbrücken

## PROGRAM COMMITTEE

- Gianfranco Bilardi, U. Padova
- Pierluigi Crescenzi, U. Firenze
- Camil Demetrescu (co-chair), Sapienza U. Rome
- Josep Diaz, UPC Barcelona
- Giuseppe Di Battista, U. Roma III
- Giorgio Gambosi, U. Rome "Tor Vergata"
- Ludek Kucera, Charles U.
- Jan van Leeuwen, Utrecht U.
- Stefano Leonardi (co-chair), Sapienza U. Rome
- Fabrizio Luccio, U. Pisa
- Alberto Marchetti-Spaccamela (co-chair), Sapienza U. Rome
- Jaroslav Nesetril, Charles U.
- Maurice Nivat, U. Paris Diderot
- Vangelis Paschos, U. Paris-Dauphine
- Franco Preparata, Brown U.
- Paul Spirakis, RACTI and U. Patras
- Leen Stougie, Free U. Amsterdam and CWI
- Peter Widmayer, ETH Zurich