Algo 2005
 Sections
  Homepage
  ESA'2005
  WABI'2005
  WAOA'2005
  ATMOS'2005
  Program
  Invited speakers
  Registration
  Accomodation
  Tourism
  Pictures
 Preliminary program

REGISTRATION
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




MONDAY ESA - 1 ESA - 2 WABI
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 Sub-Linear Comparative Time and Traffic Ratio
S. Rührup and C. Schindelhauer
Relax-and-cut for capacitated network design
G. Kliewer and L. Timajev
Dynamic De-Novo Prediction of microRNAs Associated with Cell Conditions
C. Zilberstein and M. Ziv-Ukelson
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
Linear-Time Enumeration of Isolated Cliques
H. Ito, K. Iwama and T. Osumi
Time-Window 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 Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs
S. Cabello and B. Mohar
Min Sum Clustering with Penalties
R. Hassin and E.Or
A Lookahead Branch-and-Bound 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




TUESDAY ESA - 1 ESA - 2 WABI
09:00 - 09:50 Invited talk
Cristopher Moore
09:50 - 10:00 Short break
10:00 - 10:25 Low degree connectivity in ad-hoc networks
L. Kucera
Optimal integer alphabetic trees in linear time
T. Hu and L. Larmore and J. Morgenthaler
Using Semi-Definite Programming to Enhance Supertree Resolvability
S. Moran, S. Rao and S. Snir
10:25 - 10:50 5-Regular Multi-Graphs are 3-Colorable 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 node-capacitated ring routing
A. Frank, Z. Kiraly and B. Kotnyek
Space Efficient Algorithms for the Burrows-Wheeler 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
Cache-oblivious comparison-based 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 p-Median Problems for Trees in Sub-quadratic Time
R. Benkoczi and B. Bhattacharya
Oblivious vs. Distribution-based 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 well-solvable allocation problem
A. Alfieri, S. van de Velde, G. Woeginger
Allocating memory in a lock-free 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 Higher-Order 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/O-Efficient 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 2-Approximation Algorithm for Sorting by Prefix Reversals
J. Fischer and S. Ginzinger
Efficient Approximation Schemes for Geometric Problems?
D. Marx
A 1.375-Approximation Algorithm for Sorting by Transpositions
I. Elias and T. Hartman
17:10 - 17:35 Approximating the 2-Interval 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 Signed-Binary Representations
G. Manku and J. Sawada
Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs
A. Berger, A. Czumaj, M.Grigni and H. Zhao




WEDNESDAY ESA - 1 ESA - 2 WABI
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 c-Oriented Range Searching with DOP-Trees
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
Fairness-Free 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 t-spanners
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 3-approximation algorithm for scheduling related machines
A. Kovacs
The Peres-Shields 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 Response-Time 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 Primal-Dual 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
Workload-Optimal 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 Primal-Dual to Schedule Split Intervals with Demands
R. Bar-Yehuda 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




THURSDAY ESA WAOA WABI
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 cost-splitting
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 k-Splittable Flows
R. Koch, I. Spenke and M. Skutella
Efficient Parameterized Algorithm for Biopolymer Structure-Sequence 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 Tree-Decomposed 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. Leaver-Fay, 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 Hop-optimal Network in the Weak Sensor Model
M. Farach-Colton, R. Fernandes and M. Mosteiro
On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem
S. Krumke, W. de Paepe, D. Poensgen, M. Lipmann, A. Marchetti-Spaccamela 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 min-max (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




FRIDAY WAOA ATMOS
09:10 - 09:35 Improved Approximation Algorithm for Convex Recoloring of Trees
R. Bar-Yehuda, 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. Garzon-Astolfi, 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 High-Traffic Railway Line
P. Tormos, A. Lova, L. Ingolotti, F. Barber, M. Abril, and M.A. Salido
12:10 - 12:35 A note on semi-online machine covering
T. Ebenlendr, J. Noga, J. Sgall and G. Woeginger
Computer-Based 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. Bar-Yehuda 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. Mueller-Hannemann 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 One-Parameter 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 Better-than-Greedy Algorithm for k-Set Multicover
T. Fujito and H. Kurahashi
17:35 - 18:00 Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT
A. Avidor, I. Berokovitch and U. Zwick