

SUNDAY 18:00  20:00 
Registration at Hotel Tryp Bellver 
MONDAY 12:30  13:30 
Registration at Hotel Tryp Bellver 
MONDAY 15:00  16:45 
Registration at Hotel Tryp Bellver 
07:00  11:30 
Eclipse observation (on your own) 
11:30  11:40 
Opening 
11:40  12:30 
Invited talk Giuseppe F. Italiano

12:30  12:40 
Short break 
12:40  13:25 
Exploring an unknown graph efficiently R. Fleischer and G. Trippen 
Heuristic improvements for computing max multicommodity flow and min multicut G. Batra, N. Garg and G. Gupta 
Spectral Clustering Gene Ontology Terms to Group Genes by Function N. Speer, C. Spieth and A. Zell 
13:05  13:30 
Online Routing in Faulty Meshes with SubLinear Comparative Time and Traffic Ratio S. Rührup and C. Schindelhauer 
Relaxandcut for capacitated network design G. Kliewer and L. Timajev 
Dynamic DeNovo Prediction of microRNAs Associated with Cell Conditions C. Zilberstein and M. ZivUkelson 
13:30  15:00 
Lunch 
15:00  15:25 
On the price of anarchy and stability of correlated equilibria of linear congestion games G. Christodoulou and E. Koutsoupias 
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions F. Dorn, E. Penninkx, H. Bodlaender and F. Fomin 
Clustering Gene Expression Series with Prior Knowledge L. Brehelin 
15:25  15:50 
The Complexity of Games on Highly Regular Graphs (Extended Abstract) K. Daskalakis and C. Papadimitriou 
An algorithm for the SAT problem for formulae of linear length M. Wahlström 
A Linear Time Biclustering Algorithm for Time Series Gene Expression Data S. Madeira and A. Oliveira 
15:50  16:15 
Computing Equilibrium Prices: Does Theory Meet Practice? B. Codenotti, B. McCune, R. Raman and K. Varadarajan 
LinearTime Enumeration of Isolated Cliques H. Ito, K. Iwama and T. Osumi 
TimeWindow Analysis of Developmental Gene Expression Data with Multiple Genetic Backgrounds T. Tuller, E. Oron, E. Makavy, D. Chamovitz and B. Chor 
16:15  16:45 
Break 
16:45  17:10 
Finding Shortest NonSeparating and NonContractible Cycles for Topologically Embedded Graphs S. Cabello and B. Mohar 
Min Sum Clustering with Penalties R. Hassin and E.Or 
A Lookahead BranchandBound Algorithm for the Maximum Quartet Consistency Problem G. Wu, J. You and G. Lin 
17:10  17:35 
Delineating boundaries for imprecise regions I. Reinbacher, M. Benkert, M. van Kreveld, J. Mitchell and A. Wolff 
Improved Approximation Algorithms for Metric Max TSP Z. Chen and T. Nagoya 
Computing the Quartet Distance Between Arbitrary Evolutionary Trees. C. Christiansen, C. Norgaard, S. Pedersen and M. Randers 
17:35  18:00 
EXACUS  Efficient and Exact Algorithms for Curves and Surfaces E. Berberich et al 
Unbalanced Graph Cuts A. Hayrapetyan, D. Kempe, M. Pal and Z. Svitkina 

18:00  18:05 
Short break 
18:05  19:00 
ESA Bussiness meeting 
09:00  09:50 
Invited talk Cristopher Moore 
09:50  10:00 
Short break 
10:00  10:25 
Low degree connectivity in adhoc networks L. Kucera 
Optimal integer alphabetic trees in linear time T. Hu and L. Larmore and J. Morgenthaler 
Using SemiDefinite Programming to Enhance Supertree Resolvability S. Moran, S. Rao and S. Snir 
10:25  10:50 
5Regular MultiGraphs are 3Colorable with Independent of their Size Positive Probability.
J. Díaz et al 
Predecessor Queries in Constant Time? M. Karpinski and Y. Nekrich 
From Constrained to Unconstrained Maximum Agreement Subtree in Linear Time H. Ting and Z. Peng 
10:50  11:20 
Break 
11:20  11:45 
An algorithm for nodecapacitated ring routing A. Frank, Z. Kiraly and B. Kotnyek 
Space Efficient Algorithms for the BurrowsWheeler Backtransformation U. Lauther and T. Lukovszki 
Pattern Identification in Biogeography: Metrics and Algorithms for Comparing Area Cladograms G. Ganapathy, B. Goodson, R. Jansen, V. Ramachandran and T. Warnow 
11:45  12:10 
On degree constrained shortest paths S. Khuller, K. Lee and . Shayman 
Cacheoblivious comparisonbased algorithms on multisets A. Farzan, P. Ferragina, G. Franceschini and J. Ian Munro 
On the Complexity of Several Haplotyping Problems R. Cilibrasi, L. van Iersel, S. Kelk and J. Tromp 
12:10  12:35 
A New Template for Solving pMedian Problems for Trees in Subquadratic Time R. Benkoczi and B. Bhattacharya 
Oblivious vs. Distributionbased Sorting: An Experimental Evaluation G. Chaudhry and T. Cormen 
A Hidden Markov Technique for Haplotype Reconstruction P. Rastas, M. Koivisto, H. Mannila and E. Ukkonen 
12:35  13:00 
Roll cutting in the curtain industry, or: A wellsolvable allocation problem A. Alfieri, S. van de Velde, G. Woeginger 
Allocating memory in a lockfree manner A. Gidenstam, M. Papatriantafilou and P. Tsiga 
Algorithms for Imperfect Phylogeny Haplotyping (IPPH) with a Single Homoplasy or Recombination Event Y. Song, Y. Wu and D. Gusfield 
13:00  15:00 
Lunch 
15:00  15:25 
Generating Realistic Terrains with HigherOrder Delaunay Triangulations T. de Kok, Marc van Kreveld, and M. Loffler 
New tools and simpler algorithms for branchwidth C. Paul and J. Telle 
A Faster Algorithm for Detecting Network Motifs S. Wernicke 
15:25  15:50 
I/OEfficient Construction of Constrained Delaunay Triangulations P. Agarwal, L. Arge and K. Yi 
Treewidth Lower Bounds with Brambles H. Bodlaender, A. Grigoriev and A. Koster 
Reaction Motifs in Metabolic Networks V. Lacroix, C. Gomes Fernandes and M. Sagot 
15:50  16:15 
Convex Hull and Voronoi Diagram of Additively Weighted Points C. Delage and J. Boissonnat 
Minimal interval completions P. Heggernes, K. Suchan, I. Todinca and Y. Villanger 
Reconstructing Metabolic Networks Using Interval Analysis V. Moulton and W. Tucker 
16:15  16:45 
Break 
16:45  17:10 
A 2Approximation Algorithm for Sorting by Prefix Reversals J. Fischer and S. Ginzinger 
Efficient Approximation Schemes for Geometric Problems? D. Marx 
A 1.375Approximation Algorithm for Sorting by Transpositions I. Elias and T. Hartman 
17:10  17:35 
Approximating the 2Interval Pattern problem M. Crochemore, D. Hermelin, G. Landau and S. Vialette 
Geometric clustering to minimize the sum of cluster sizes V. Bilo, I. Caragiannis, C. Kaklamanis and P. Kanellopoulos 
A New Tight Upper Bound on the Transposition Distance A. Labarre 
17:35  18:00 
A Loopfree Gray Code for Minimal SignedBinary Representations G. Manku and J. Sawada 
Approximation Schemes for Minimum 2Connected Spanning Subgraphs in Weighted Planar Graphs A. Berger, A. Czumaj, M.Grigni and H. Zhao 

09:00  09:50 
Invited talk Marino Zerial 
09:50  10:00 
Short break 
10:00  10:25 
Packet Routing and Information Gathering in Lines, Rings and Trees Z. Azar and R. Zachut 
Efficient cOriented Range Searching with DOPTrees M. de Berg, H. Haverkort and M. Streppel 
Perfect Sorting by Reversals is Not Always Difficult S. Berard, A. Bergeron, C. Chauve and C. Paul 
10:25  10:50 
Jitter Regulation for Multiple Streams D. Hay and G. Scalosub 
Matching Point Sets with respect to the Earth Mover's Distance S. Cabello, P. Giannopoulos, C. Knauer and G. Rote 
Minimum Recombination Histories by Branch and Bound R. Lyngsoe, Y. Song and J. Hein 
10:50  11:20 
Break 
11:20  11:45 
Small stretch spanners on dynamic graphs G. Ausiello and Paolo G. Franciosa and Giuseppe F. Italiano 
Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delay A. Fishkin, K. Jansen, S. Sevastianov and R. Sitters 
A Unifying Framework for Seed Sensitivity and Its Application to Subset Seeds G. Kucherov, L. Noe and M. Roytberg 
11:45  12:10 
An Experimental Study of Algorithms for Fully Dynamic Transitive Closure I. Krommidas and C. Zaroliagis 
FairnessFree Periodic Scheduling J. Sgall, H. Shachnai and T. Tamir 
Generalized Planted (l,d)Motif Problem with Negative Set H. Leung and F. Chin 
12:10  12:35 
Experimental study of geometric tspanners M. Farshi and J. Gudmundsson 
Online Bin Packing with Cardinality Constraints L. Epstein 
Alignment of Tandem Repeats with Excision, Duplication, Substitution and Indels (EDSI) M. Sammeth, T. Weniger, D. Harmsen and J. Stoye 
12:35  13:00 
Highway Hierarchies Hasten Exact Shortest Path Queries P. Sanders and D. Schultes 
Fast monotone 3approximation algorithm for scheduling related machines A. Kovacs 
The PeresShields Order Estimator for Fixed and Variable Length Markov Chains with Applications to DNA Sequence Similarity D. Dalevi and D. Dubhashi 
13:00  15:00 
Lunch 
15:00  15:25 
Engineering Planar Separator Algorithms M. Holzer, G. Prasinos, F. Schulz, D. Wagner and C. Zaroliagis 
An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees F. Cicalese and E. Laber 
Multiple Structural RNA Alignment with Lagrangian Relaxation M. Bauer, G. Klau and K. Reinert 
15:25  15:50 
Stxxl: Standard Template Library for XXL Data Sets R. Dementiev, L. Kettner and P. Sanders 
Online View Maintenance under a ResponseTime Constraint K. Munagala, J. Yang and H. Yu 
Faster Algorithms for Optimal Multiple Sequence Alignment based on Pairwise Comparisons P. Agarwal, Y. Bilu and R. Kolodny 
15:50  16:15 
Negative Cycle Detection dennis chihim wong and Y. C. Tam 
Online PrimalDual Algorithms for Covering and Packing Problems N. Buchbinder and J. Naor 
Ortholog Clustering on a Multipartite Graph A. Vashist, C. Kulikowski and I. Muchnik 
16:15  16:45 
Break 
16:45  17:10 
Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information Y. Bejerano, J. Naor and A. Sprintson 
WorkloadOptimal Histograms on Streams S. Muthukrishnan, M. Strauss and X. Zheng 
Linear Time Algorithm for Parsing RNA Secondary Structure B. Rastegari and A. Condon 
17:10  17:35 
Using Fractional PrimalDual to Schedule Split Intervals with Demands R. BarYehuda and D. Rawitz 
Finding Frequent Patterns in a String in Sublinear Time P. Berenbrink, F. Ergun and T. Friedetzky 
A Compressed Format for Collections of Phylogenetic Trees and Improved Consensus Performance R. Boyer, W. Hunt and S. Nelesen 
17:35  18:00 
An approximation algorithm for the minimum latency set cover problem R. Hassin and A. Levin 
Online Occlusion Culling G.Frahling and J. Krokowski 


Conference dinner 
09:00  09:50 
Invited talk Seffi Naor 
09:50  10:00 
Short break 
10:00  10:25 
Shortest Paths in Matrix Multiplication Time P. Sankowski 
The Hardness of Network Design for Unsplittable Flow with Selfish Users Y. Azar and A. Epstein 
Optimal protein threading by costsplitting P. Veber, N. Yanev, R. Andonov and V. Poirriez 
10:25  10:50 
Computing common intervals of K permutations, with applications to modular decomposition of graphs A. Bergeron, C. Chauve, F. de Montgolfier, M. Raffinot 
Approximation and Complexity of kSplittable Flows R. Koch, I. Spenke and M. Skutella 
Efficient Parameterized Algorithm for Biopolymer StructureSequence Alignment Y. Song, C. Liu, X. Huang, R. Malmberg, Y. Xu and L. Cai 
10:50  11:20 
Break 
11:20  11:45 
Greedy Routing in TreeDecomposed Graphs P. Fraigniaud 
The conference call search problem in wireless networks L. Epstein and A. Levin 
Rotamer/Rotamer Energy Calculations Using a Trie Data Structure A. LeaverFay, J. Snoeyink and B. Kuhlman 
11:45  12:10 
Making Chord Robust to Byzantine Attacks A. Fiat, J. Saia and M. Young 
SONET ADMs minimization with divisible paths L. Epstein and A. Levin 
Improved Maintenance of Molecular Surfaces using Dynamic Graph Connectivity E. Eyal and D. Halperin 
12:10  12:35 
Bucket Game with Applications to Set Multicover and Dynamic Page Migration M. Bienkowski and J. Byrka 
Deterministic Online Optical Call Admission Revisited S. Krumke and E. Gassner 
The Main Structural Regularities of the Sandwich Proteins A. Kister, T. Fokas, T. Papatheodorou and I. Gelfand 
12:35  13:00 
Bootstrapping a Hopoptimal Network in the Weak Sensor Model M. FarachColton, R. Fernandes and M. Mosteiro 
On Minimizing the Maximum Flow Time in the Online DialaRide Problem S. Krumke, W. de Paepe, D. Poensgen, M. Lipmann, A. MarchettiSpaccamela and L. Stougie 
Discovery of Protein Substructures in EM Maps K. Lasker, O. Dror, H. Wolfson and R. Nussinov 
13:00  15:00 
Lunch 
15:00  15:25 
Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs A. Björklund 
Approximation Schemes for Packing with Item Fragmentation H. Shachnai, T. Tamir and O. Yehezkely 

15:25  15:50 
A Cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem A. Faye and F. Roupin 
Online Removable Square Packing X. Han, K. Iwama and G. Zhang 

15:50  16:15 
Approximation complexity of minmax (regret) versions of shortest path, spanning tree, and knapsack H. Aissi, C. Bazgan and D. Vanderpooten 
The Online Target Date Assignment Problem S. Heinz, Sven O Krumke, N. Megow, J. Rambau, A. Tuchscherer and T. Vredeveld 

16:15  16:45 
Break 
16:45  17:10 
Complexity of Robust Approximate Zeros V. Sharma, Z. Du and C. Yap 
Tighter Approximations on Greedy for Maximum Induced Matchings in Regular Graphs M. Lewenstein and Z. Gotthilf 

17:10  17:35 
Optimizing a 2D Function Satisfying Unimodality Properties E. Demaine and S. Langerman 
`Almost stable' matchings in the Roommates problem D. Abraham, P. Biro and D. Manlove 

17:35  18:00 

A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs T. Nieberg and J. Hurink 

09:10  09:35 

Improved Approximation Algorithm for Convex Recoloring of Trees R. BarYehuda, I. Feldman and D. Rawitz 
Invited talk Frank Geraets (aka F. Wagner) and Ludger Palz, Deutche Bahn AG Optimizing the configuration of stations along the German railway network

09:35  10:00 

On the Minimum Load Coloring Problem N. Ahuja, A. Baltz, B. Doerr, A. Privetivy and A. Srivastav 
10:00  10:25 

Partial Multicuts in Trees D. Segev and A. Levin 
Station Location  Complexity and Approximation S. Mecke, A. Schoebel, and D. Wagner 
10:25  10:50 

On Approximating Restricted Cycle Covers B. Manthey 
Line Planning with Minimal Traveling Time A. Schoebel and S. Scholl 
10:50  11:20 
Break 
11:20  11:45 

Speed Scalingof Tasks with Precedence Constraints K. Pruhs, R. van Stee and P. Uthaisombut 
Parameter Analysis of Transfers in the Rapid Transit Network Design R. García, A. GarzonAstolfi, A. Marín, J.A. Mesa, and F.A. Ortega 
11:45  12:10 

Scheduling Parallel Jobs with Linear Speedup A. Grigoriev and M. Uetz 
A Genetic Approach to Train Scheduling on a HighTraffic Railway Line P. Tormos, A. Lova, L. Ingolotti, F. Barber, M. Abril, and M.A. Salido 
12:10  12:35 

A note on semionline machine covering T. Ebenlendr, J. Noga, J. Sgall and G. Woeginger 
ComputerBased Decision Support for Railway Traffic Scheduling and Dispatching: a Review of Models and Algorithms. J. Tornquist 
12:35  13:00 

Exploiting Locality: Approximating Sorting Buffers R. BarYehuda and J. Laserson 
Engine Assignment Problem Under Some Operation Policy for Railway Transportation. T. Illes, M. Makai, and Z. Vaik 
13:00  15:00 
Lunch 
15:00  15:25 

On the Hardness and Approximate Fair Cost Allocation in Metric TSP Games M. Blaeser and S. Lakshminarayanan 
Paying Less for Train Connections with MOTIS M. MuellerHannemann and M. Schnee 
15:25  15:50 

Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost D. Fotakis, S. Kontogiannis and P. Spirakis 
Applying Analytical and Empirical Methods to the Assessment of Railway Capacity M. Abril, F. Barber, L. Ingolotti, M.A. Salido, P. Tormos, and A. Lova 
15:50  16:15 

Improvements for Truthful Mechanisms with Verifiable OneParameter Selfish Agents A. Ferrante, G. Parlato, F. Sorrentino and C. Ventre 

16:15  16:45 
Break 
16:45  17:10 

Rounding of Sequences and Matrices, with Applications B. Doerr, T. Friedrich, C. Klein and R. Osbild 

17:10  17:35 

A BetterthanGreedy Algorithm for kSet Multicover T. Fujito and H. Kurahashi 

17:35  18:00 

Improved Approximation Algorithms for MAX NAESAT and MAX SAT A. Avidor, I. Berokovitch and U. Zwick 


