ALCOM-FT Technical Reports

Jaume Baixeries and Jose Balcazar
Discrete Deterministic Data Mining as Knowledge Compilation
Barcelona. Work packages 1 and 4. December 2003.

Debora Donato, Luigi Laura, Stefano Leonardi and Stefano Millozzi
Large scale properties of the Webgraph
Rome. Work package 1. December 2003.

Gemma Casas-Garriga
Statistical Strategies for Pruning All the Uninteresting Association Rules
Barcelona. Work packages 1 and 4. December 2003.

Jaume Baixeries, Gemma Casas-Garriga and Jose Luis Balcazar
A Best-First Strategy For Finding Frequent Sets
Barcelona. Work packages 1 and 4. December 2003.

Gemma Casas-Garriga
Discovering Unbounded Episodes in Sequential Data
Barcelona. Work packages 1 and 4. December 2003.

Gemma Casas-Garriga
Towards a formal Framework for mining Mining General Patterns from Structured Data
Barcelona. Work packages 1 and 4. December 2003.

Peter Verbaan, Jan van Leeuwen and Jirí Wiedermann
Lineages of Automata
Utrecht. Work package 4. December 2003.

Kristoffer Arnsfelt Hansen
Constant width planar computation characterizes ACC⁰
Århus. Work package 4. December 2003.

Thomas Wolle
A Framework for Network Reliability Problems on Graphs of Bounded Treewidth
Utrecht. Work package 2. December 2003.

Ann Vandevelde, Han Hoogeveen, Cor Hurkens and Jan Karel Lenstra
Lower bounds for the head-body-tail problem on parallel machines: a computational study of the multiprocessor flow shop
Utrecht. Work package 3. December 2003.

Marjan van den Akker and Han Hoogeveen
Minimizing the number of tardy jobs
Utrecht. Work package 3. December 2003.

Han Hoogeveen
Multicriteria scheduling
Utrecht. Work package 3. December 2003.

Andreas Brandstädt, Hans L. Bodlaender, Dieter Kratsch, Michaël Rao and Jeremy Spinrad
On Algorithms for (P₅,Gem)-Free Graphs
Utrecht. Work package 2. December 2003.

Hans L. Bodlaender and Gerard Tel
Rectilinear Graphs and Angular Resolution
Utrecht. Work package 2. December 2003.

Ioannis Caragiannis and Christos Kaklamanis
Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks
Patras. Work packages 2 and 4. December 2003.

Devdatt Dubashi, Luigi Laura and Alessandro Panconesi
Analysis and Experimental Evaluation of a simple Algorithm for Collaborative Filtering
Rome. Work package 1. December 2003.

Luigi Laura, Umberto Nanni and Fabiano Sarracco
Query Transformation through approximated LSI computation
Rome. Work package 1. December 2003.

Ernst Althaus, Fritz Eisenbrand, Stefan Funke and Kurt Mehlhorn
Point Containment in the Integer Hull of a Polyhedron
MPI. Work package 4. December 2003.

Tassos Dimitriou, Sotiris Nikoletseas and Paul Spirakis
The Infection Time of Graphs
Patras. Work packages 2 and 4. December 2003.

Torsten Fahle and Meinolf Sellmann
Cost based Filtering for the Constrained Knapsack Problem
Paderborn. Work packages 3 and 4. December 2003.

Sotiris Nikoletseas and Paul Spirakis
How to certify in deterministic polynomial time the high chromatic number of instances of sparse random graphs
Patras. Work package 4. December 2003.

Torsten Fahle
Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique
Paderborn. Work packages 3 and 4. December 2003.

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
Distributed Communication Algorithms for Ad-hoc Mobile Networks
Patras. Work package 2. December 2003.

Azzedine Boukerche and Sotiris Nikoletseas
Algorithmic Design for Communication in Mobile Ad hoc Networks
Patras. Work package 2. December 2003.

Charilaos Efthymiou, Sotiris Nikoletseas and Jose Rolim
Energy Balanced Data Propagation in Wireless Sensor Networks.
Patras. Work package 2. December 2003.

Thanasis Antoniou, Azzedine Boukerche, Ioannis Chatzigiannakis, George Mylonas and Sotiris Nikoletseas
A New Energy Efficient and Fault-tolerant Protocol for Data Propagation in Smart Dust Networks using Varying Transmission Range
Patras. Work packages 2 and 5. December 2003.

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
Efficient and Robust Protocols for Local Detection and Propagation in Smart Dust Networks
Patras. Work package 2. December 2003.

Meinolf Sellmann and Torsten Fahle
Constraint Programming based Lagrangian Relaxation for the Automatic Recording Problem
Paderborn. Work package 4. December 2003.

Sven Grothklags
Fleet Assignment with Connection Dependent Ground Times
Paderborn. Work package 3. December 2003.

Azzedine Boukerche and Sotiris Nikoletseas
Protocols for Data Propagation in Wireless Sensor Networks: A Survey
Patras. Work package 2. December 2003.

Maria Andreou and Paul Spirakis
Efficient Colouring of Squares of Planar Graphs
Patras. Work packages 2 and 4. December 2003.

Sotiris Nikoletseas and Paul Spirakis
Distributed Algorithms for Representative Problems in Ad-hoc Mobile Environments: A Critical Survey
Patras. Work package 2. December 2003.

Maria Andreou, Sotiris Nikoletseas and Paul Spirakis
Algorithms and Experiments on Colouring Squares of Planar Graphs
Patras. Work packages 2, 4 and 5. December 2003.

Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou
Simple On-line Algorithms for Call Control in Cellular Networks
Patras. Work packages 2 and 4. December 2003.

Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano and Anastasios Sidiropoulos
Fractional and Integral Coloring of Locally-Symmetric Sets of Paths on Binary Trees
Patras. Work packages 2 and 4. December 2003.

Ioannis Chatzigiannakis, Tassos Dimitriou, Sotiris Nikoletseas and Paul Spirakis
A Probabilistic Algorithm for Efficient and Robust Data Propagation in Smart Dust Networks
Patras. Work packages 2 and 5. December 2003.

Ioannis Chatzigiannakis, Tassos Dimitriou, Marios Mavronicolas, Sotiris Nikoletseas and Paul Spirakis
A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks
Patras and Cyprus. Work packages 2 and 5. December 2003.

Ioannis Chatzigiannakis, Elena Kaltsa and Sotiris Nikoletseas
On the Effect of User Mobility and Density on the Performance of Protocols for Ad-hoc Mobile Networks
Patras. Work packages 2 and 5. December 2003.

Ioannis Chatzigiannakis, Michael Markou and Sotiris Nikoletseas
Distributed Circle Formation for Anonymous Oblivious Robots
Patras. Work packages 2 and 5. December 2003.

Sotiris Nikoletseas, Ioannis Chatzigiannakis, Athanasios Antoniou, Haris Euthimiou, Athanasios Kinalis and George Mylonas
Energy Efficient Protocols for Sensing Multiple Events in Smart Dust Networks
Patras. Work packages 2 and 5. December 2003.

Ioannis Chatzigiannakis and Sotiris Nikoletseas
A Sleep-Awake Protocol for Information Propagation in Smart Dust Networks
Patras. Work packages 2 and 5. December 2003.

Jens S. Kohrt and Kirk Pruhs
A constant approximation algorithm for sorting buffers
Århus. Work package 4. December 2003.

Martin Gairing, Thomas Lücking, Marios Mavronicolas and Burkhard Monien
Computing Nash Equilibria for Scheduling on Restricted Parallel Links
Paderborn and Cyprus. Work package 2. December 2003.

Sotiris Nikoletseas, Vicky Papadopoulou and Paul Spirakis
Radiocoloring Graphs via the Probabilistic Method
Patras. Work packages 2 and 4. December 2003.

Ioannis Caragiannis, Christos Kaklamanis and Panagiotis Kanellopoulos
Energy-Efficient Wireless Network Design
Patras. Work packages 2 and 4. December 2003.

Dimitris Fotakis
Incremental Algorithms for Facility Location and k-Median
Patras. Work packages 1 and 4. December 2003.

Ioannis Chatzigiannakis, Athanasios Kinalis, Athanasios Poulakidas, Grigorios Prasinos and Christos Zaroliagis
DAP: A Generic Platform for the Simulation of Distributed Algorithms
Patras. Work packages 2 and 5. December 2003.

Alexis Kaporis, Christos Makris, Spyros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas and Christos Zaroliagis
Improved Bounds for Finger Search on a RAM
Patras. Work package 4. December 2003.

Sotiris Nikoletseas, Grigorios Prasinos, Paul Spirakis and Christos Zaroliagis
Attack Propagation in Networks
Patras. Work packages 2 and 5. December 2003.

Robert Elsässer and Burkhard Monien
Load Balancing of Unit Size Tokens and Expansion Properties of Graphs
Paderborn. Work package 2. December 2003.

Robert Elsässer and Burkhard Monien
Diffusion Load Balancing in Static and Dynamic Networks
Paderborn. Work package 2. December 2003.

Robert Elsässer, Rastislav Královic and Burkhard Monien
Sparse Topologies with Small Spectrum Size
Paderborn. Work package 2. December 2003.

Stefan Bertels and Torsten Fahle
A Hybrid Setup for a Hybrid Scenario: Combining Heuristics for the Home Health Care Problem
Paderborn. Work package 3. December 2003.

Thomas Decker, Thomas Lücking and Burkhard Monien
A 5/4-approximation algorithm for scheduling identical malleable tasks
Paderborn. Work package 4. December 2003.

Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien and Manuel Rode
Nashification and the Coordination Ratio for a Selfish Routing Game
Paderborn. Work package 2. December 2003.

Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien and Manuel Rode
Selfish Routing in Non-cooperative Networks: A Survey
Paderborn. Work package 2. December 2003.

Robert Elsässer, Thomas Lücking and Burkhard Monien
On Spectral Bounds for the k-Partitioning of Graphs
Paderborn. Work package 2. December 2003.

Stefan Schamberger and Jens-Michael Wierum
Graph Partitioning in Scientific Simulations: Multilevel Schemes vs. Space-Filling Curves
Paderborn. Work package 2. December 2003.

Stefan Schamberger
Improvements to the Helpful-Set Heuristic and a New Evaluation Scheme for Graphs-Partitioners
Paderborn. Work package 2. December 2003.

Stefan Schamberger
Heuristic Graph Bisection with Less Restrictive Balance Constraints
Paderborn. Work package 2. December 2003.

Martin Gairing, Thomas Lucking, Marios Mavronicolas, Burkhard Monien and Paul Spirakis
The Structure and Complexity of Extreme Nash Equilibria
Paderborn, Patras and Cyprus. Work packages 2 and 4. December 2003.

Thomas Lucking, Marios Mavronicolas, Burkhard Monien, Manuel Rode, Paul Spirakis and Imrich Vrto
Which is the Worst-case Nash Equilibrium?
Paderborn, Patras and Cyprus. Work packages 2 and 4. December 2003.

Costas Busch, Malik-Mgdon Ismail, Marios Mavronicolas and Roger Wattenhofer
Greedy ~O(C+D) Hot-Potato Routing on Trees
Cyprus. Work packages 2 and 4. December 2003.

Thomas Lucking, Marios Mavronicolas, Burkhard Monien and Manuel Rode
A New model for Selfish Routing
Paderborn and Cyprus. Work packages 2 and 4. December 2003.

Dimitrios Koukopoulos, Marios Mavronicolas, Sotiris Nikoletseas and Paul Spirakis
The Impact of Network Structure on the Stability of Greedy Protocols
Patras and Cyprus. Work packages 2 and 4. December 2003.

Dimitrios Koukopoulos, Marios Mavronicolas and Paul Spirakis
Performance and Stability Bounds for Dynamic Networks
Patras and Cyprus. Work packages 2 and 4. December 2003.

Dimitrios Koukopoulos, Marios Mavronicolas and Paul Spirakis
Instability of Networks with Quasi-Static Link Capacities
Patras and Cyprus. Work packages 2 and 4. December 2003.

Costas Busch, Marios Mavronicolas and Paul Spirakis
The Cost of Concurrent, Low-contention Read-Modify-Write
Patras and Cyprus. Work packages 2 and 4. December 2003.

Costas Busch, Malik-Magdon Ismail, Marios Mavronicolas and Paul Spirakis
An Analysis of Direct Routing - Why do we need Buffers?
Patras and Cyprus. Work packages 2 and 4. December 2003.

Jan Klein and Gabriel Zachmann
ADB-Trees: Controlling the Error of Time-Critical Collision Detection
Paderborn. Work package 5. December 2003.

Jan Klein and Gabriel Zachmann
Time-Critical Collision Detection Using an Average-Case Approach
Paderborn. Work package 5. December 2003.

Harald Räcke
Minimizing Congestion in General Networks
Paderborn. Work package 2. December 2003.

Klaus Volbert
A Simulation Environment for Ad Hoc Networks using Sector Subdivision
Paderborn. Work packages 2 and 5. December 2003.

Friedhelm Meyer auf der Heide, Christian Schindelhauer, Klaus Volbert and Matthias Grünewald
Congestion, Dilation, and Energy in Radio Networks
Paderborn. Work package 2. December 2003.

Matthias Grünewald, Tamás Lukovszki, Christian Schindelhauer and Klaus Volbert
Distributed Maintenance of Resource Efficient Wireless Network Topologies
Paderborn. Work package 2. December 2003.

Stefan Rührup, Christian Schindelhauer, Klaus Volbert and Matthias Grünewald
Performance of Distributed Algorithms for Topology Control in Wireless Networks
Paderborn. Work packages 2 and 5. December 2003.

Christian Schindelhauer, Tamás Lukovszki, Stefan Rührup and Klaus Volbert
Worst Case Mobility in Ad Hoc Networks
Paderborn. Work package 2. December 2003.

Hans L. Bodlaender and Arie M. C. A. Koster
Safe separators for treewidth
Utrecht. Work packages 2 and 5. December 2003.

Frank van den Eijkhof, Hans L. Bodlaender and Arie M.C.A. Koster
Safe reduction rules for weighted treewidth
Utrecht. Work packages 2 and 5. December 2003.

Hans L. Bodlaender, Hajo J. Broersma, Fedor V. Fomin, Artem V. Pyatkin and Gerhard J. Woeginer
Radio labeling with pre-assigned frequencies
Utrecht. Work package 2. December 2003.

Hans L. Bodlaender, Arie M.C.A. Koster and Frank van den Eijkhof
Pre-Processing Rules for Triangulation of Probabilistic Networks
Utrecht. Work package 5. December 2003.

Luigi Laura, Stefano Leonardi, Stefano Millozzi, Ulrich Meyer and Jop Sibeyn
Algorithms and Experiments for the Webgraph
Rome and MPI. Work packages 1 and 5. December 2003.

Stefano Leonardi and Guido Schäfer
Cross-Monotonic Cost-Sharing Methods for Connected Facility Location Games
Rome and MPI. Work packages 2 and 4. December 2003.

Roman Dementiev, Lutz Kettner, Jens Mehnert and Peter Sanders
Engineering a Sorted List Data Structure for 32 Bit Keys
MPI. Work package 5. December 2003.

André Brinkmann, Friedhelm Meyer auf der Heide, Kay Salzwedel, Christian Scheideler, Mario Vodisek and Ulrich Rückert
Storage Management as Means to cope with Exponential Information Growth
Paderborn. Work package 1. December 2003.

Marcin Bienkowski, Miroslaw Korzeniowski and Harald Räcke
A Practical Algorithm for Constructing Oblivious Routing Schemes
Paderborn. Work package 2. December 2003.

Kay Salzwedel
Algorithmic Approaches for Storage Networks
Paderborn. Work package 1. December 2003.

Holger Bast, Kurt Mehlhorn, Guido Schäfer and Hisao Tamaki
A Heuristic for Dijkstra's Algorithm with Many Targets and its Use inWeighted Matching Algorithms
MPI. Work package 5. November 2003.

Friedrich Eisenbrand, Stefan Funke, Joachim Reichel and Elmar Schömer
Packing a Trunk
MPI. Work packages 4 and 5. November 2003.

Annamaria Kovacs
Sum-Multicoloring on Paths
MPI. Work packages 2 and 4. November 2003.

Holger Bast, Kurt Mehlhorn, Guido Schäfer and Hisao Tamaki
Matching Algorithms are Fast in Sparse Random Graphs
MPI. Work package 4. November 2003.

Guido Schäfer and Naveen Sivadasan
Topology Matters: Smoothed Competitiveness of Metrical Task Systems
MPI. Work package 4. November 2003.

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer and Tjark Vredeveld
Scheduling to minimize flow time metrics
Rome and MPI. Work packages 2 and 4. November 2003.

P. Jonsson and A. Krokhin
Computational complexity of auditing finite attributes in statistical databases
Warwick. Work packages 1 and 4. November 2003.

Paul Wilfred Goldberg
Bounds for the Convergence Rate of Randomized Local Search in a Multiplayer, Uniform Resource Sharing Game
Warwick. Work package 4. November 2003.

Fedor V. Fomin and Dimitrios M. Thilikos
A Simple and Fast Approach for Solving Problems on Planar Graphs
Barcelona. Work packages 2 and 4. November 2003.

M. Blesa and C. Blum
Ant Colony Optimization for the maximum disjoint paths problem
Barcelona. Work packages 2, 3 and 5. November 2003.

Albert Atserias and María Luisa Bonet
On the Automatizability of Resolution and Related Propositional Proof Systems
Barcelona. Work package 4. November 2003.

L. Becchetti, J. Könemann and S. Leonardi
Sharing the cost more efficiently: Improved Approximation for Multicommodity Rent-or-Buy
Rome. Work package 2. November 2003.

Gerth Stølting Brodal, Rolf Fagerberg, Thomas Mailund, Christian N. S. Pedersen and Derek Phillips
Speeding Up Neighbour-Joining Tree Construction
Århus. Work package 5. November 2003.

Gerth Stølting Brodal, Rolf Fagerberg and Kristoffer Vinther
Engineering a Cache-Oblivious Sorting Algorithm
Århus. Work packages 1 and 5. November 2003.

Philippe Flajolet and Robert Sedgewick
Analytic Combinatorics: Basic Complex Asymptotics
INRIA. Work package 4. November 2003.

Magali Lescot and Mireille Régnier
Motif statistics on plants datasets
INRIA. Work package 5. November 2003.

Mireille Régnier and Alain Denise
Rare Events and Conditional Events on Random Strings
INRIA. Work packages 1 and 4. November 2003.

Michael Jünger, Sebastian Leipert and Merijam Percan
Triangulating Clustered Graphs
Cologne. Work package 4. November 2003.

Christoph Buchheim and Michael Jünger
An Integer Programming Approach to Fuzzy Symmetry Detection
Cologne. Work package 4. November 2003.

Frauke Liers, Michael Jünger, Gerhard Reinelt and Giovanni Rinaldi
Computing Exact Ground-States of Hard Ising Spin-Glass
Cologne. Work package 4. November 2003.

Wilhelm Barth, Petra Mutzel and Michael Jünger
Simple and Efficient Bilayer Crosscounting
Cologne. Work package 4. November 2003.

Harald Räcke, Christian Sohler and Matthias Westermann
Online Scheduling for Sorting Buffers
Paderborn. Work package 4. November 2003.

Artur Czumaj, Funda Ergun, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld and Christian Sohler
Sublinear-Time Approximation of Euclidean Minimum Spanning Tree
Paderborn. Work packages 1 and 4. November 2003.

Artur Czumaj and Christian Sohler
Abstract Combinatorial Programs and Efficient Property Testers
Paderborn. Work packages 1 and 4. November 2003.

Alexander Tiskin
Packing tripods: narrowing the density gap
Warwick. Work packages 4 and 5. November 2003.

Valentina Damerow, Harald Räcke, Friedhelm Meyer auf der Heide, Christian Scheideler and Christian Sohler
Smoothed Motion Complexity
Paderborn. Work package 4. November 2003.

Martin Ziegler
Fast Relative Approximation of Potential Fields
Paderborn. Work package 1. November 2003.

Frédéric Chyzak
Algorithms Seminar, 2001-2002
INRIA. Work packages 2 and 4. November 2003.

P. Berenbrink, L. A. Goldberg, P. Goldberg and R. Martin
Utilitarian Resource Assignment
Warwick. Work package 4. November 2003.

L. A. Goldberg, R. Martin and M. Paterson
Sampling 10-colourings of the triangular lattice
Warwick. Work package 4. November 2003.

Josep Díaz, Mathew Penrose, Jordi Petit and Maria Serna
Approximating Layout Problems on Random Geometric Graphs
Barcelona. Work packages 2, 4 and 5. November 2003.

Jordi Petit
Combining Spectral Sequencing and Parallel Simulated Annealing for the MinLA Problem
Barcelona. Work packages 1, 4 and 5. November 2003.

Eythan Levy, Guy Louchard and Jordi Petit
A distributed algorithm to find Hamiltonian cycles in G_n,p random graphs
Barcelona. Work packages 2 and 4. November 2003.

Albert Atserias and Víctor Dalmau
A Combinatorial Characterization of Resolution Width
Barcelona. Work package 4. November 2003.

Anna Gal and Peter Bro Miltersen
The cell probe complexity of succinct data structures
Århus. Work package 4. November 2003.

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen and V Vinay
Circuits on Cylinders
Århus. Work package 4. November 2003.

Jesper Makholm Byskov
Chromatic Number in Time O(2.4023ⁿ) Using Maximal Independent Sets
Århus. Work package 4. November 2003.

Jesper Makholm Byskov, Bolette Ammitzbøll Madsen and Bjarke Skjernaa
New Algorithms for Exact Satisfiability
Århus. Work package 4. November 2003.

Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono and Alejandro López-Ortiz
The Cost of Cache-Oblivious Searching
Århus. Work packages 1 and 4. November 2003.

Gerth Stølting Brodal and Rolf Fagerberg
Lower Bounds for External Memory Dictionaries
Århus. Work packages 1 and 4. November 2003.

Gerth Stølting Brodal and Rolf Fagerberg
On the Limits of Cache-Obliviousness
Århus. Work packages 1 and 4. November 2003.

Gerth Stølting Brodal, Rolf Fagerberg, Anna Östlin, Christian N. S. Pedersen and S. Srinivasa Rao
Computing Refined Buneman Trees in Cubic Time
Århus. Work package 4. November 2003.

Luca Becchetti
Modeling Temporal Locality in Paging: A tighter Analysis of LRU and FWF
Rome. Work package 4. November 2003.

Fedor V. Fomin and Dimitrios M. Thilikos
Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-up
Barcelona. Work packages 2 and 4. October 2003.

MohammadTaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde and Dimitrios M. Thilikos
Fast approximation schemes for K_3,3-minor-free or K₅-minor-free graphs
Barcelona. Work packages 2 and 4. October 2003.

Lali Barrière, Pierre Fraigniaud, Nicola Santoro and Dimitrios M. Thilikos
Connected and Internal Graph Searching
Barcelona. Work packages 2 and 4. October 2003.

Hans L. Bodlaender, Michael R. Fellows and Dimitrios M. Thilikos
Derivation of algorithms for cutwidth and related graph layout parameters
Barcelona and Utrecht. Work packages 2 and 4. October 2003.

Erik D. Demaine, MohammadTaghi Hajiaghayi, Fedor V. Fomin and Dimitrios M. Thilikos
Fixed-Parameter Algorithms for the (k,r)-Center in Planar Graphs and Map Graphs
Barcelona. Work packages 2, 3 and 4. October 2003.

Fedor V. Fomin and Dimitrios M. Thilikos
Dominating sets and local treewidth
Barcelona. Work packages 2 and 4. October 2003.

Fedor V. Fomin and Dimitrios M. Thilikos
New upper bounds on the decomposability of planar graphs and fixed parameter algorithms
Barcelona. Work packages 2 and 4. October 2003.

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos
Bidimensional Parameters and Local Treewidth
Barcelona. Work packages 2 and 4. October 2003.

Josep Díaz, Maria Serna and Dimitrios M. Thilikos
Counting List H-Colorings and Variants
Barcelona. Work packages 2 and 4. October 2003.

Rene Beier and Berthold Vöcking
Random Knapsack in Expected Polynomial Time
MPI. Work package 4. October 2003.

Ulrich Meyer and Norbert Zeh
I/O Efficient Undirected Shortest Paths
MPI. Work packages 1 and 4. October 2003.

Rene Beier and Berthold Vöcking
Probabilistic Analysis of Knapsack Core Algorithms
MPI. Work package 4. October 2003.

Rene Beier, Artur Czumaj, Piotr Krysta and Berthold Vöcking
Computing Equilibria for Congestion Games with (Im)perfect Information
MPI. Work packages 2 and 4. October 2003.

Csanad Imreh
Scheduling problems on two sets of identical machines
MPI. Work package 4. October 2003.

A. Krokhin and P. Jonsson
Recognizing frozen variables in constraint satisfaction problems
Warwick. Work package 4. October 2003.

D. Cohen, M. Cooper, P. Jeavons and A. Krokhin
Identifying efficiently solvable cases of non-Boolean Max CSP
Warwick. Work package 4. October 2003.

D. Cohen, M. Cooper, P. Jeavons and A. Krokhin
Multimorphisms: Classifying the complexity of soft constraints
Warwick. Work package 4. October 2003.

F. Boerner, A. Bulatov, P. Jeavons and A. Krokhin
Quantified constraints: Algorithms and complexity
Warwick. Work package 4. October 2003.

A. Krokhin and B. Larose
Solving order constraints in logarithmic space
Warwick. Work package 4. October 2003.

A. Krokhin, P. Jeavons and P. Jonsson
Reasoning about temporal relations: The maximal tractable subalgebras of Allen's interval algebra
Warwick. Work package 4. October 2003.

A. Krokhin, P. Jeavons and P. Jonsson
Constraint satisfaction problems on intervals and lengths
Warwick. Work package 4. October 2003.

Conrado Martínez
Partial Quicksort
Barcelona. Work package 4. September 2003.

Vincenzo Bonifaci, Benedetto A. Colombo, Camil Demetrescu, Irene Finocchi and Luigi Laura
A System for Building Animated Presentations over the Web
Rome. Work package 5. September 2003.

M. Adler, P. Berenbrink, T. Friedetzky, L. A. Goldberg, P. Goldberg and M. Paterson
A Proportionate Fair Scheduling Rule with Good Worst-case Performance
Warwick. Work package 4. September 2003.

L. A. Goldberg, R. Martin and M. Paterson
Random sampling of 3-colourings in Z²
Warwick. Work package 4. September 2003.

L. A. Goldberg, M. Jerrum and M. Paterson
The computational complexity of two-state spin systems
Warwick. Work package 4. September 2003.

Ricard Gavaldà and Denis Thérien
Algebraic Characterizations of Small Classes of Boolean Functions
Barcelona. Work package 4. September 2003.

J. Díaz, M. Serna and N. Wormald
Computation of the bisection width for random d-regular graphs
Barcelona. Work packages 2 and 4. September 2003.

J. Díaz, N. Do, M. Serna and N. Wormald
Bounds on the max and min bisection of random cubic and random 4-regular graphs
Barcelona. Work packages 2 and 4. September 2003.

J. Gabarró, A. A. Stewart, M. Clint, E. Boyle and I. Vallejo
Computational models for Web- and Grid-based computation
Barcelona. Work package 4. September 2003.

A. Stewart, M. M. Clint and J. Gabarró
Barrier Synchronisation: axiomatisation and relaxation
Barcelona. Work package 4. September 2003.

Ivan B. Damgård and Gudmund Skovbjerg Frandsen
An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates
Århus. Work package 4. September 2003.

Ivan Bjerre Damgård and Gudmund Skovbjerg Frandsen
Efficient Algorithms for gcd and Cubic Residuosity in the Ring of Eisenstein Integers
Århus. Work package 4. September 2003.

Giorgio Ausiello, Cristina Bazgan, Marc Demange and Vangelis Th. Paschos
Completeness in differential approximation classes
Rome. Work package 4. September 2003.

C. Blum and M. Blesa
New Metaheuristic Approaches for the Edge-Weighted k-Cardinality Tree Problem
Barcelona. Work packages 3, 4 and 5. September 2003.

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer and Tjark Vredeveld
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
Rome and MPI. Work packages 2 and 4. September 2003.

Peter Bro Miltersen, Jaikumar Radhakrishnan and Ingo Wegener
On converting CNF to DNF
Århus. Work package 4. November 2003.

Klaus Meer
On the complexity of some problems in interval arithmetic
Århus. Work package 4. September 2003.

Klaus Meer
On consistency and width notions for constraint programs with algebraic constraints
Århus. Work package 4. September 2003.

Joan Boyar, Lene M. Favrholdt and Kim S. Larsen
The Relative Worst Order Ratio Applied to Paging
Århus. Work package 4. September 2003.

Jens S. Frederiksen and Kim S. Larsen
On-Line Seat Reservations via Off-Line Seating Arrangements
Århus. Work package 3. September 2003.

Roman Dementiev and Peter Sanders
Asynchronous Parallel Disk Sorting
MPI. Work packages 1 and 5. September 2003.

Juha Kärkkäinen and Peter Sanders
Simple Linear Work Suffix Array Construction
MPI. Work packages 1 and 4. September 2003.

Stefan Funke, Domagoj Matijevic and Peter Sanders
Approximating Energy Efficient Paths in Wireless Multi-Hop Networks
MPI. Work packages 2 and 4. September 2003.

Irit Katriel and Sven Thiel
Fast Bound Consistency for the Global Cardinality Constraint
MPI. Work package 4. September 2003.

Dimitris Fotakis, Rasmus Pagh, Peter Sanders and Paul Spirakis
Space Efficient Hash Tables With Worst Case Constant Access Time
Århus, Patras and MPI. Work packages 4 and 5. September 2003.

Dimitris Fotakis
On the Competitive Ratio for Online Facility Location
MPI. Work package 4. September 2003.

Stefan Burkhardt and Juha Kärkkäinen
Fast Lightweight Suffix Array Construction and Checking
MPI. Work packages 1, 4 and 5. September 2003.

Giorgio Ausiello, Paolo G. Franciosa and Giuseppe F. Italiano
Fully dynamic maintenance of t-spanners on general graphs
Rome. Work packages 2 and 4. September 2003.

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela and Kirk Pruhs
Semi-clairvoyant Scheduling
Rome. Work packages 2 and 4. September 2003.

Joan Boyar and Lene M. Favrholdt
The Relative Worst Order Ratio for On-Line Bin Packing Algorithms
Århus. Work package 4. September 2003.

Nadia Ben Azzouna, Christine Fricker and Fabrice Guillemin
Modeling ADSL traffic on an IP backbone link
INRIA. Work package 2. August 2003.

Camil Demetrescu and Irene Finocchi
Combinatorial Algorithms for Feedback Problems in Directed Graphs
Rome. Work package 4. August 2003.

Marianne Durand and Philippe Flajolet
Loglog Counting of Large Cardinalities
INRIA. Work packages 1 and 5. July 2003.

James A. Fill, Philippe Flajolet and Nevin Kapur
Singularity Analysis, Hadamard Products, and Tree Recurrences
INRIA. Work package 4. July 2003.

Philippe Flajolet, Joaquim Gabarró and Helmut Pekari
Analytic Urns
Barcelona and INRIA. Work package 4. July 2003.

Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer
Boltzmann Sampler for the Random Generation of Combinatorial Structures
INRIA. Work packages 4 and 5. July 2003.

Viviane Baladi and Brigitte Vallée
Euclidean Algorithms are Gaussian
INRIA. Work package 4. July 2003.

Jacqueline Boyer, Fabrice Guillemin, Philippe Robert and Bert Zwart
Heavy tailed M/G/1-PS queues with impatience and admission control in packet networks
INRIA. Work package 2. July 2003.

Fabrice Guillemin, Philippe Robert and Bert Zwart
Tail Asymptotics for Processor Sharing Queues
INRIA. Work package 2. July 2003.

Vincent Dumas, Fabrice Guillemin and Philippe Robert
Admission control of leaky bucket regulated sources in a queueing system with priority
INRIA. Work package 2. July 2003.

Joan Boyar and Lene M. Favrholdt
The Relative Worst Order Ratio for On-Line Algorithms
Århus. Work package 4. July 2003.

Camil Demetrescu, Stefano Emiliozzi and Giuseppe F. Italiano
Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms
Rome. Work packages 2, 4 and 5. July 2003.

Vladimir Deineko and Alexander Tiskin
The Double-Tree Approximation for Metric TSP: Is The Best Good Enough?
Warwick. Work packages 3, 4 and 5. June 2003.

Alexander Tiskin
Packing tripods: A computational approach
Warwick. Work packages 4 and 5. June 2003.

Alexander Tiskin
Communication-Efficient Parallel Gaussian Elimination
Warwick. Work packages 1 and 4. June 2003.

Conrado Martínez and Xavier Molinero
An Efficient Generic Algorithm for the Generation of Unlabelled Cycles
Barcelona. Work package 4. June 2003.

Conrado Martínez and Xavier Molinero
Generic Algorithms for the Generation of Combinatorial Objects
Barcelona. Work package 4. June 2003.

Gerth Stølting Brodal, Erik D. Demaine and J. Ian Munro
Fast Allocation and Deallocation with an Improved Buddy System
Århus. Work package 4. May 2003.

Conrado Martínez, Daniel Panario and Alfredo Viola
Adaptive Sampling for Quickselect
Barcelona. Work packages 1 and 4. April 2003.

Camil Demetrescu and Irene Finocchi
A Portable Virtual Machine for Program Debugging and Directing
Rome. Work package 5. March 2003.

Ioannis Caragiannis, Christos Kaklamanis and Panagiotis Kanellopoulos
New Results for Energy-Efficient Broadcasting in Wireless Networks
Patras. Work packages 2 and 4. December 2002.

Philippe Flajolet, Bruno Salvy and Gilles Schaeffer
Airy Phenomena and Analytic Combinatorics of Connected Graphs
INRIA. Work package 4. October 2002.

Philippe Flajolet, Wojciech Szpankowski and Brigitte Vallée
Hidden Word Statistics
INRIA. Work packages 1 and 4. October 2002.

Paul Spirakis and Christos Zaroliagis
Distributed Algorithm Engineering
Patras. Work packages 2 and 5. August 2002.

Josep Díaz, Jordi Petit and Maria Serna
Random scaled sector graphs
Barcelona. Work packages 2 and 4. June 2002.

Insup Lee, Jin-Young Choi, Hee Hwan Kwak, Anna Philippou and Oleg Sokolsky
A Family of Resource-Bound Real-time Process Algebras
Cyprus. Work package 4. June 2002.

Anna Philippou, Oleg Sokolsky, Insup Lee, Rance Cleaveland and Scott Smolka
Hiding Resources that Can Fail: An Axiomatic Perspective
Cyprus. Work package 4. June 2002.

Insup Lee, Anna Philippou and Oleg Sokolsky
Formal Modeling and Analysis of Power-Aware Real-Time Systems
Cyprus. Work package 4. June 2002.

Gerth Stølting Brodal and Rolf Fagerberg
Funnel Heap - A Cache Oblivious Priority Queue
Århus. Work packages 1 and 4. June 2002.

Tobias Polzin and Siavash Vahdati Daneshmand
Extending Reduction Techniques for the Steiner Tree Problem
MPI. Work packages 2 and 5. June 2002.

Meinolf Sellmann, Georg Kliewer and Achim Koberstein
Capacitated Network Design - Cardinality Cuts and Coupled Variable Fixing Algorithms based on Lagrangian Relaxations
Paderborn. Work packages 2 and 3. June 2002.

Ernst Althaus, Alexander Bockmayr, Matthias Elf, Michael Jünger, Thomas Kasper and Kurt Mehlhorn
SCIL - Symbolic Constraints in Integer Linear Programming
Cologne and MPI. Work package 4. May 2002.

Albert Atserias
The Complexity of Resource-Bounded Propositional Proofs
Barcelona. Work package 4. May 2002.

Albert Atserias, Nicola Galesi and Pavel Pudlák
Monotone Simulations of Nonmonotone Proofs
Barcelona. Work package 4. May 2002.

Jérémie Bourdon and Brigitte Vallée
Generalized Pattern Matching Statistics
INRIA. Work packages 1 and 4. May 2002.

Albert Atserias
Unsatisfiable Random Formulas are Hard to Certify
Barcelona. Work package 4. May 2002.

Marianne Durand
Asymptotic Analysis of an Optimized Quicksort Algorithm
INRIA. Work package 5. May 2002.

Carsten Gutwenger, Michael Jünger, Sebastian Leipert, Petra Mutzel, Merijam Percan and René Weiskircher
Advances in C-Planarity Testing of Clustered Graphs
Cologne. Work package 4. May 2002.

Carsten Gutwenger, Michael Jünger, Sebastian Leipert, Petra Mutzel, Merijam Percan and René Weiskircher
Subgraph Induced Planar Connectivity Augmentation
Cologne. Work package 4. May 2002.

Wilhelm Barth, Michael Jünger and Petra Mutzel
Simple and Efficient Bilayer Cross Counting
Cologne. Work package 4. May 2002.

André Brinkmann, Kay Salzwedel and Christian Scheideler
Compact, Adaptive Placement Schemes for Non-Uniform Distribution Requirements
Paderborn. Work package 1. May 2002.

Philippe Flajolet and Robert Sedgewick
Analytic Combinatorics, Symbolic Combinatorics
INRIA. Work package 4. May 2002.

Albert Atserias
Improved Bounds for the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
Barcelona. Work package 4. May 2002.

G. Casas-Garriga
A Multi-Step Pruning Strategy to Remove Uninteresting Association Rules
Barcelona. Work packages 1 and 4. May 2002.

E. Alba, F. Almeida, M. Blesa, J. Cabeza, C. Cotta, M. Díaz, I. Dorta, J. Gabarró, C. León, J. Luna, L. Moreno, C. Pablos, J. Petit, A. Rojas and F. Xhafa
MALLBA: A library of skeletons for combinatorial optimisation
Barcelona. Work packages 4 and 5. May 2002.

R. Baeza-Yates, J. Gabarró and X. Messeguer
Fringe Analysis of Synchronized Parallel Insertion Algorithms in 2-3 Trees
Barcelona. Work package 4. May 2002.

J. Gabarró, A. Stewart and M. Clint
Grab and Go Systems: a CPO approach to concurrent web and grid-based computation
Barcelona. Work package 4. May 2002.

J. Díaz, J. Nesetril, M. Serna and D.M. Thilikos
H-colorings of Large Degree Graphs
Barcelona. Work package 4. May 2002.

Ricard Gavaldà and Osamu Watanabe
Sequential Sampling Algorithms: Unified Analysis and Lower Bounds
Barcelona. Work package 1. May 2002.

José Balcázar
Rules with Bounded Negations and the Coverage Inference Scheme
Barcelona. Work package 1. May 2002.

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
Smart Dust Local Detection and Propagation Protocols
Patras. Work package 2. May 2002.

Erik D. Demaine, MohammadTaghi Hajiaghayi and Dimitrios Thilikos
1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
Barcelona. Work package 2. May 2002.

Erik D. Demaine, MohammadTaghi Hajiaghayi and Dimitrios M. Thilikos
Exponential Speedup of Fixed Parameter Algorithms on K_3,3-minor-free or K₅-minor-free Graphs
Barcelona. Work package 2. May 2002.

Naomi Nishimura, Prabhakar Ragde and Dimitrios M. Thilikos
Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
Barcelona. Work package 2. May 2002.

Elias Koutsoupias, Marios Mavronicolas and Paul Spirakis
Approximate Equilibria and Ball Fusion
Patras and Cyprus. Work packages 2 and 4. May 2002.

Meinolf Sellmann and Warwick Harvey
Heuristic Constraint Propagation (Using Local Search for Incomplete Pruning and Domain Filtering of Redundant Constraints for the Social Golfer Problem)
Paderborn. Work packages 3 and 4. May 2002.

Ulf Lorenz and Burkhard Monien
The Secret of Selective Game Tree Search, when Using Random-Error Evaluations
Paderborn. Work package 4. May 2002.

Ulf Lorenz
Parallel Controlled Conspiracy Number Search
Paderborn. Work packages 2 and 4. May 2002.

Torsten Fahle
Cost Based Filtering vs. Upper Bounds for Maximum Clique
Paderborn. Work packages 3 and 4. May 2002.

Josep Díaz, Maria Serna and Dimitrios M. Thilikos
(H,C,K)-coloring: Fast, Easy and Hard cases
Barcelona. Work packages 2 and 4. May 2002.

Carme Àlvarez, Maria Blesa and Maria Serna
A characterization of universal stability for directed graphs in the adversarial queueing model
Barcelona. Work packages 2 and 4. May 2002.

Carme Àlvarez, Maria Blesa and Maria Serna
Universal stability of undirected graphs in the adversarial queueing model
Barcelona. Work packages 2 and 4. May 2002.

J. Díaz, N. Do, M. J. Serna and N. C. Wormald
Bisection of Random Cubic Graphs
Barcelona. Work package 4. May 2002.

Josep Díaz, Maria Serna and Dimitrios Thilikos
The complexity of restrictive H-coloring
Barcelona. Work packages 2 and 4. May 2002.

Dimitrios Koukopoulos, Sotiris Nikoletseas and Paul Spirakis
Stability Issues in Heterogeneous and FIFO Networks under the Adversarial Queueing Model
Patras. Work package 2. May 2002.

Giuseppe Cattaneo, Pompeo Faruolo, Umberto Ferraro-Petrillo and Giuseppe F. Italiano
Maintaining Dynamic Minimum Spanning Trees: An Experimental Study
Rome. Work package 5. May 2002.

Robert Elsässer, Burkhard Monien, Stefan Schamberger and Günter Rote
Toward optimal diffusion matrices
Paderborn. Work package 2. May 2002.

Sergei Bezrukov and Robert Elsässer
Edge-Isoperimetric Problems for Cartesian Powers of Regular Graphs
Paderborn. Work package 2. May 2002.

Robert Elsässer, Burkhard Monien and Robert Preis
Diffusion Schemes for Load Balancing on Heterogeneous Networks
Paderborn. Work package 2. May 2002.

Tomas Plachetka
Perfect Load-Balancing (Demand-Driven) Parallel Ray Tracing
Paderborn. Work package 2. May 2002.

Tomas Plachetka, Olaf Schmidt and Frank Albracht
The HiQoS Rendering System
Paderborn. Work package 5. May 2002.

Luca Becchetti, Suhas Diggavi, Stefano Leonardi, Alberto Marchetti-Spaccamela, Muthu Muthukrishnan, Thiaga Nandagopal and Andrea Vitaletti
Parallel scheduling problems in next generation wireless networks
Rome. Work package 2. May 2002.

C. Demetrescu and G.F. Italiano
A New Approach to Dynamic All Pairs Shortest Paths
Rome. Work package 4. May 2002.

Torsten Fahle, Stefan Schamberger and Meinolf Sellmann
Symmetry Breaking
Paderborn. Work packages 3 and 4. May 2002.

Thomas Lücking, Burkhard Monien and Manuel Rode
On the Problem of Scheduling Flows on Distributed Networks
Paderborn. Work package 2. May 2002.

Maria Andreou and Paul Spirakis
The Square of Any Planar Graph is an Almost Perfect Graph
Patras. Work packages 2 and 4. May 2002.

Ernst Althaus and Christian Fink
A Polyhedral Approach to Surface Reconstruction from Planar Contours
MPI. Work package 4. May 2002.

Jesper Makholm Nielsen
On the Number of Maximal Independent Sets in a Graph
Århus. Work package 4. May 2002.

Dimitrios Koukopoulos, Marios Mavronicolas and Paul Spirakis
The Impact of Structure on Stability in Adversarial Queueing Theory
Patras and Cyprus. Work packages 2 and 4. May 2002.

Fabrice Guillemin, Philippe Robert and Bert Zwart
Performance of TCP in the presence of correlated packet loss
INRIA. Work package 2. May 2002.

José L. Balcázar, Yang Dai and Osamu Watanabe
Provably fast support vector regression using random sampling
Barcelona. Work package 1. May 2002.

Marjan van den Akker and Han Hoogeveen
Minimizing the number of late jobs in case of stochastic processing times
Utrecht. Work package 3. May 2002.

Marjan van den Akker, Han Hoogeveen and Gerhard J. Woeginger
The two-machine open shop problem: to fit, or not to fit, that was the question
Utrecht. Work package 3. May 2002.

Bolette Ammitzbøll Madsen, Jesper Makholm Nielsen and Bjarke Skjernaa
On the Number of Maximal Bipartite Subgraphs of a Graph
Århus. Work package 4. May 2002.

K.M.J. De Bontridder, B.V. Halldórsson, M.M. Halldórsson, J.K. Lenstra, R. Ravi and L. Stougie
Approximation algorithms for the minimum test set problem
Utrecht. Work package 3. May 2002.

K.M.J. De Bontridder, J.K. Lenstra, J.B. Orlin and L. Stougie
Branch and bound algorithms for the minimum test set problem
Utrecht. Work package 3. May 2002.

K.M.J. De Bontridder
A purchase lot sizing problem with quantity discounts
Utrecht. Work package 3. May 2002.

Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis and Kostas Tsichlas
Optimal Finger Search Trees in the Pointer Machine
Århus and Patras. Work package 4. May 2002.

Stephen Alstrup, Gerth Stølting Brodal, Inge Li Gørtz and Theis Rauhe
Time and Space Efficient Multi-Method Dispatching
Århus. Work package 4. May 2002.

Alexis Kaporis, Lefteris Kirousis and Yannis Stamatiou
How to prove conditional randomness using the Principle of Deferred Decisions
Patras. Work package 4. May 2002.

Dimitrios Koukopoulos, Marios Mavronicolas, Sotiris Nikoletseas and Paul Spirakis
On the Stability of Compositions of Universally Stable, Greedy Contention-Resolution Protocols
Patras and Cyprus. Work packages 2 and 4. May 2002.

Ioannis Chatzigiannakis and Sotiris Nikoletseas
An Adaptive Compulsory Protocol for Basic Communication in Highly Changing Ad hoc Mobile Networks
Patras. Work package 2. May 2002.

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
On the Average and Worst-case Efficiency of Some New Distributed Algorithms for Communication and Control in Ad-hoc Mobile Networks
Patras. Work packages 2 and 4. May 2002.

Ioannis Chatzigiannakis, Sotiris Nikoletseas, Paul Spirakis and Christos Zaroliagis
Experimenting with Relay Protocols for Communication in Ad-hoc Mobile Networks
Patras. Work packages 2 and 5. May 2002.

Frank Schulz, Dorothea Wagner and Christos Zaroliagis
Using Multi-Level Graphs for Timetable Information in Railway Systems
Patras. Work packages 3 and 5. May 2002.

Christos Zaroliagis
Implementations and Experimental Studies of Dynamic Graph Algorithms
Patras. Work package 5. May 2002.

Maria Andreou, Dimitris Fotakis, Sotiris Nikoletseas, Vicky Papadopoulou and Paul Spirakis
On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-completeness and Approximations
Patras and MPI. Work packages 2 and 4. May 2002.

Mary Cryan and Peter Bro Miltersen
On Pseudorandom generators in NC⁰
Århus. Work package 4. May 2002.

Anna Östlin and Rasmus Pagh
One-Probe Search
Århus. Work package 4. May 2002.

Bengt Mueck, Wilhelm Dangelmaier, Matthias Fischer and Wolfram Klemisch
Bi-directional Coupling of Simulation Tools with a Walkthrough System
Paderborn. Work package 5. May 2002.

Jan Klein, Jens Krokowski, Matthias Fischer, Rolf Wanka and Friedhelm Meyer auf der Heide
The Randomized Sample Tree: A Data Structure for Externally Stored 3D-Scenes
Paderborn. Work package 5. May 2002.

Arie M. C. A. Koster, Hans L. Bodlaender and C. P. M. van Hoesel
Treewidth: Computational Experiments
Utrecht. Work packages 3 and 4. May 2002.

Hans L. Bodlaender and Udi Rotics
Computing the treewidth and the minimum fill-in with the modular decomposition
Utrecht. Work package 4. May 2002.

Fariza Tahi, Manolo Gouy and Mireille Régnier
Automatic RNA secondary structure prediction with a comparative approach
INRIA. Work package 1. June 2002.

Jens S. Frederiksen and Kim S. Larsen
Packet Bundling
Århus. Work packages 2 and 4. May 2002.

Leah Epstein and Lene M. Favrholdt
On-Line Maximizing the Number of Items Packed in Variable-Sized Bins
Århus. Work package 4. May 2002.

Leah Epstein and Lene M. Favrholdt
Optimal Non-Preemptive Semi-Online Scheduling on Two Related Machines
Århus. Work packages 3 and 4. May 2002.

Leah Epstein and Lene M. Favrholdt
Optimal Preemptive Semi-Online Scheduling to Minimize Makespan on Two Related Machines
Århus. Work packages 3 and 4. May 2002.

Susanne Albers, Lene M. Favrholdt and Oliver Giel
On Paging with Locality of Reference
Århus. Work packages 4 and 5. May 2002.

Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin and Christian N. S. Pedersen
Solving the String Statistics Problem in Time O(nlog n)
Århus. Work package 4. May 2002.

Gerth Stølting Brodal, Rolf Fagerberg and Christian N. S. Pedersen
Computing the Quartet Distance between Evolutionary Trees in Time O(n log n)
Århus. Work package 4. May 2002.

Gerth Stølting Brodal, Rolf Fagerberg and Riko Jacob
Cache Oblivious Search Trees via Binary Trees of Small Height
Århus. Work packages 1, 4 and 5. May 2002.

Gerth Stølting Brodal and Rolf Fagerberg
Cache Oblivious Distribution Sweeping
Århus. Work packages 1 and 4. May 2002.

Stefan Edelkamp and Ulrich Meyer
Theory and Practice of Time-Space Trade-Offs in Memory Limited Search
MPI. Work packages 1 and 4. May 2002.

Ulrich Meyer
Buckets Strike Back: Improved Parallel Shortest-Paths
MPI. Work packages 1 and 2. May 2002.

Jop Sibeyn, James Abello and Ulrich Meyer
Heuristics for Semi-External Depth First Search on Directed Graphs
MPI. Work package 1. May 2002.

Kurt Mehlhorn and Ulrich Meyer
External-Memory Breadth-First Search with Sublinear I/O
MPI. Work package 1. May 2002.

Nicolas Beldiceanu, Qi Guo and Sven Thiel
Non-overlapping Constraints between Convex Polytopes
MPI. Work package 3. May 2002.

Olaf Bonorden, Friedhelm Meyer auf der Heide and Rolf Wanka
Composition of Efficient NestedBSP Algorithms: Minimum Spanning Tree Computation as an InstructiveExample
Paderborn. Work package 2. May 2002.

Rolf Wanka
Any Load-Balancing Regimen for Evolving TreeComputations on CirculantGraphs is Asymptotically Optimal
Paderborn. Work package 2. May 2002.

Artur Czumaj and Christian Sohler
Property Testing with Geometric Queries
Paderborn. Work package 4. May 2002.

Juha Kärkkäinen
Computing the Threshold for q-Gram Filters
MPI. Work packages 1 and 4. May 2002.

Kurt Mehlhorn, Volker Priebe, Guido Schäfer and Naveen Sivadasan
All-Pairs Shortest-Paths Computation in the Presence of Negative Cycles
MPI. Work packages 2 and 4. May 2002.

Stefan Burkhardt and Juha Kärkkäinen
One-gapped q-Gram Filters for Levenshtein Distance
MPI. Work packages 1, 4 and 5. May 2002.

Alon Itai and Irit Katriel
Implicit dictionaries for internal and external memory
MPI. Work packages 1 and 4. May 2002.

Spyros Kontogiannis
Multiple Choice Assignments for Uniformly Related Machines
MPI. Work packages 2 and 4. May 2002.

Tobias Polzin and Siavash Vahdati Daneshmand
Partitioning Techniques for the Steiner Problem
MPI. Work packages 2 and 5. May 2002.

Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas and Paul Spirakis
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game
Patras, MPI and Cyprus. Work packages 2 and 4. May 2002.

Hannah Bast
Scheduling at Twilight the Easy Way
MPI. Work packages 2 and 4. May 2002.

Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler and Berthold Vöcking
Randomized Pursuit-Evasion in Graphs
Paderborn and MPI. Work packages 2 and 4. May 2002.

Tobias Polzin and Siavash Vahdati Daneshmand
On Steiner Trees and Minimum Spanning Trees in Hypergraphs
MPI. Work packages 2 and 5. May 2002.

Peter Sanders and Jesper Larsson Träff
The Hierarchical Factor Algorithm for All-to-all Communication
MPI. Work packages 1 and 2. May 2002.

René Beier, Peter Sanders and Naveen Sivadasan
Energy Optimal Routing in Radio Networks Using Geometric Data Structures
MPI. Work package 2. May 2002.

Peter Sanders and Berthold Vöcking
Random Arc Allocation and Applications
MPI. Work packages 1 and 4. May 2002.

Peter Sanders and Kurt Mehlhorn
Scanning Multiple Sequences Via Cache Memory
MPI. Work packages 1, 4 and 5. May 2002.

David A. Bader, Bernard M.E. Moret and Peter Sanders
High-Performance Algorithm Engineering for Parallel Computation
MPI. Work packages 2 and 5. May 2002.

Leah Epstein, Csanád Imreh and Rob van Stee
More on weighted servers or FIFO is better than LRU
MPI. Work packages 2 and 4. May 2002.

Artur Czumaj and Berthold Vöcking
Tight Bounds for Worst-Case Equilibria
MPI. Work packages 2 and 4. May 2002.

Bela Csaba, Marek Karpinski and Piotr Krysta
Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems
MPI. Work packages 2 and 4. May 2002.

Artur Czumaj, Piotr Krysta and Berthold Vöcking
Selfish Traffic Allocation for Server Farms
MPI. Work packages 2 and 4. May 2002.

Cyril Banderier and Donatella Merlini
Lattice paths with an infinite set of jumps
INRIA and MPI. Work package 4. May 2002.

Albert Atserias, Maria Luisa Bonet and Juan Luis Esteban
Lower Bounds for the Weak Pigeonhole Principle and Random Formulas Beyond Resolution
Barcelona. Work package 4. May 2002.

Cyril Banderier
Limit laws for basic parameters of lattice paths with unbounded jumps
INRIA and MPI. Work package 4. May 2002.

Cyril Banderier, Kurt Mehlhorn and Rene Beier
Average case analysis of three combinatorial algorithms under limited randomness
INRIA and MPI. Work package 4. May 2002.

M. Dyer, L. A. Goldberg and M. Jerrum
Counting and sampling H-colourings
Warwick. Work package 4. May 2002.

M. Cryan, M. Dyer, L. A. Goldberg, M. Jerrum and R. Martin
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
Warwick. Work package 4. May 2002.

Leslie Ann Goldberg, Steven Kelk and Mike Paterson
The complexity of choosing an H-colouring (nearly) uniformly at random
Warwick. Work package 4. May 2002.

Fedor V. Fomin, Martín Matamala and Ivan Rapaport
The complexity of approximating the oriented diameter of chordal graphs
Paderborn. Work package 4. May 2002.

Hajo Broersma, Fedor V. Fomin, Jaroslav Nesetril and Gerhard J. Woeginger
More about subcolorings
Paderborn. Work package 4. May 2002.

Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl and Gerhard J. Woeginger
Planar graph coloring with forbidden subgraphs: Why trees and paths are dangerous.
Paderborn. Work package 4. May 2002.

Hans L. Bodlaender and Fedor V. Fomin
Tree decompositions with small cost
Paderborn and Utrecht. Work package 4. May 2002.

Fedor V. Fomin and Andrzej Lingas
Approximation algorithms for time-dependent orienteering
Paderborn. Work package 4. May 2002.

Hans L. Bodlaender and Fedor V. Fomin
Approximation of pathwidth of outerplanar graphs
Paderborn and Utrecht. Work package 4. May 2002.

Giorgio Ausiello, Paolo G. Franciosa and Daniele Frigioni
Partially Dynamic Maintenance of Minimum Weight Hyperpaths
Rome. Work package 4. April 2002.

Fabrice Guillemin, Philippe Robert and Bert Zwart
AIMD algorithms and exponential functionals
INRIA. Work packages 2 and 4. April 2002.

Christine Fricker, Philippe Robert and Danielle Tibi
A degenerate central limit theorem for single resource loss systems
INRIA. Work package 2. April 2002.

Predag Jelenkovic, Petar Momcilovic and Bert Zwart
Reduced Load Equivalence under Subexponentiality
INRIA. Work package 2. April 2002.

Fréderic Chyzak
Algorithms Seminar, 2000-2001
INRIA. Work package 4. April 2002.

J. Baixeries and G Casas-Garriga
Sampling Strategies for Finding Frequent Sets
Barcelona. Work package 1. April 2002.

Giorgio Ausiello, Paolo G. Franciosa and Daniele Frigioni
Directed Hypergraphs: Problems, Algorithmic Results, and a Novel Decremental Approach
Rome. Work package 4. March 2002.

Joan Boyar, Lene M. Favrholdt, Kim S. Larsen and Morten N. Nielsen
Extending the Accommodating Function
Århus. Work package 4. March 2002.

Joan Boyar, Susan Krarup and Morten N. Nielsen
Seat Reservation Allowing Seat Changes
Århus. Work packages 3 and 4. March 2002.

Joan Boyar, René Peralta and Denis Pochuev
Concrete Conjunctive Complexity of Symmetric Functions
Århus. Work package 4. January 2002.

C. Demetrescu and G.F. Italiano
Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths
Rome. Work package 4. January 2002.

Paul W. Goldberg
Estimating a Boolean Perceptron from its Average Satisfying Assignment: A Bound on the Precision Required
Warwick. Work package 4. December 2001.

Paul W. Goldberg
When Can Two Unsupervised Learners Achieve PAC Separation?
Warwick. Work package 4. December 2001.

Marco Gori and Klaus Meer
A step towards a complexity theory for dynamical systems
Århus. Work package 4. December 2001.

Ivan Bjerre Damgård and Gudmund Skovbjerg Frandsen
An Extended Quadratic Frobenius Primality Test with Average Case Error Estimates
Århus. Work package 4. December 2001.

Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer
Random Sampling from Boltzmann Principles
INRIA. Work package 5. December 2001.

Cyril Banderier and Philippe Flajolet
Basic Analytic Combinatorics of Directed Lattice Paths
INRIA. Work package 4. December 2001.

Conrado Martínez, Daniel Panario and Alfredo Viola
Analysis of Quickfind with small subfiles
Barcelona. Work package 4. November 2001.

Kim S. Larsen
Relaxed Red-Black Trees with Group Updates
Århus. Work package 4. November 2001.

Amalia Duch and Conrado Martínez
On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures
Barcelona. Work packages 1, 4 and 5. November 2001.

Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes, Pino Persiano and Herve Rivano
Approximate Constrained Bipartite Edge Coloring
Patras. Work package 4. October 2001.

Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou
Randomized Call Control in Sparse Wireless Cellular Networks
Patras. Work packages 2 and 4. October 2001.

Ioannis Caragiannis, Christos Kaklamanis and Panagiotis Kanellopoulos
New Bounds on the Size of the Minimum Feedback Vertex Set in Meshes and Butterflies
Patras. Work packages 2 and 4. October 2001.

Fedor V. Fomin, Dieter Kratsch and Haiko Müller
Algorithms for graphs with small octopus
Paderborn. Work package 4. October 2001.

Fedor V. Fomin, Dieter Kratsch and Jean-Christophe Novelli
Approximating minimum cocolourings
Paderborn. Work package 4. October 2001.

Vincent Dumas, Fabrice Guillemin and Philippe Robert
A Markovian analysis of AIMD algorithms
INRIA. Work packages 2 and 4. October 2001.

Vincent Dumas, Fabrice Guillemin and Philippe Robert
Effective bandwidths in a multiclass priority queueing system
INRIA. Work package 2. October 2001.

C. Demetrescu, I. Finocchi and J. T. Stasko
Specifying Algorithm Visualizations: Interesting Events or State Mapping?
Rome. Work package 5. October 2001.

Gerth Stølting Brodal and Riko Jacob
Time-dependent networks as models to achieve fast exact time-table queries
Århus. Work package 4. September 2001.

Camil Demetrescu and Mikkel Thorup
Oracles for Distances Avoiding a Link-failure
Rome. Work packages 2 and 4. September 2001.

Berthold Vöcking
Almost optimal permutation routing on hypercubes
MPI. Work packages 2 and 4. August 2001.

Peter Sanders and Jop Sibeyn
A Bandwidth Latency Tradeoff for Broadcast and Reduction
MPI. Work packages 1 and 2. August 2001.

Jakob Pagter
On Ajtai's Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem
Århus. Work package 4. June 2001.

Lars Arge and Jakob Pagter
I/O-Space Trade-Offs
Århus. Work packages 1 and 4. June 2001.

Ricard Gavaldà and Denis Thérien
Learning expressions over monoids
Barcelona. Work packages 1 and 4. June 2001.

Friedhelm Meyer auf der Heide and Rolf Wanka
Parallel Bridging Models and Their Impact on Algorithm Design
Paderborn. Work package 2. June 2001.

Marni Mishna
Attribute Grammars and Automatic Complexity Analysis
INRIA. Work package 4. June 2001.

Salvador Roura
A New Method for Balancing Binary Search Trees
Barcelona. Work package 4. June 2001.

Fedor V. Fomin and Dimitrios M. Thilikos
On the Monotonicity of Games Generated by Symmetric Submodular Functions
Barcelona. Work packages 2 and 4. June 2001.

M.J. Blesa, P. Moscato and F. Xhafa
A Memetic Algorithm for the Minimum Weighted k-Cardinality Tree Subgraph Problem"
Barcelona. Work packages 4 and 5. June 2001.

Lene Monrad Favrholdt and Morten Nyhave Nielsen
On-Line Edge-Coloring with a Fixed Number of Colors
Århus. Work packages 2 and 4. June 2001.

Jan van Leeuwen and Jiri Wiedermann
On the Power of Interactive Computing
Utrecht. Work package 4. June 2001.

Jan van Leeuwen and Jiri Wiedermann
On Algorithms and Interaction
Utrecht. Work package 4. June 2001.

Jan van Leeuwen and Jiri Wiedermann
A Computational Model of Interaction in Embedded Systems
Utrecht. Work package 4. June 2001.

Jan van Leeuwen and Jiri Wiedermann
The Turing Machine Paradigm in Contemporary Computing
Utrecht. Work package 4. June 2001.

Alain Denise, Mireille Régnier and Mathias Vandenbogaert
Assessing statistical significance of overrepresented oligonucleotides
INRIA. Work packages 1 and 4. June 2001.

Mireille Régnier, Alexandre Lifanov and Vsevolod Makeev
Three variations on word counting
INRIA. Work package 4. June 2001.

Jordi Petit
Layout Problems
Barcelona. Work packages 2, 4 and 5. June 2001.

A. Stewart, M. Clint and J. Gabarró
Algebraic rules for reasoning about BSP programs
Barcelona. Work package 4. June 2001.

M.J. Blesa, Ll. Hernandez and F. Xhafa
Parallel Skeletons for Tabu Search Method Based on Search Strategies and Neighborhood Partition
Barcelona. Work package 4. June 2001.

Funda Ergun, S. Cenk Sahinalp, Jonathan Sharp and Rakesh K. Sinha
Biased Skip Lists for Highly Skewed Access Patterns
Warwick. Work packages 4 and 5. June 2001.

Funda Ergun, S. Cenk Sahinalp, Jonathan Sharp and Rakesh K. Sinha
Biased Dictionaries with Fast Insert/Deletes
Warwick. Work package 4. June 2001.

M.J. Blesa, Ll. Hernàndez and F. Xhafa
Parallel Skeletons for Tabu Search Method
Barcelona. Work package 4. June 2001.

M.J. Blesa and F. Xhafa
A Skeleton for the Tabu Search Metaheuristic with Applications to Problems in Software Engineering
Barcelona. Work package 4. June 2001.

C. Demetrescu and G.F. Italiano
Fully Dynamic All Pairs Shortest Paths with Real Edge Weights
Rome. Work packages 2 and 4. June 2001.

C. Demetrescu, I. Finocchi, G.F. Italiano and S. Naeher
Visualization in Algorithm Engineering: Tools and Techniques
Rome. Work package 5. June 2001.

C. Demetrescu and I. Finocchi
Removing Cycles for Minimizing Crossings
Rome. Work packages 4 and 5. June 2001.

C. Demetrescu
Fully Dynamic Algorithms for Path Problems on Directed Graphs
Rome. Work packages 2, 4 and 5. June 2001.

Graham Cormode, S. Muthukrishnan and Süleyman Cenk Sahinalp
Permutation Editing and Matching via Embeddings
Warwick. Work package 4. June 2001.

Arun Jagota, Rune Bang Lyngsø and Christian Nørgaard Storm Pedersen
Comparing Stochastic Models
Århus. Work package 4. June 2001.

Rune Bang Lyngsø and Christian Nørgaard Storm Pedersen
Complexity of Comparing Hidden Markov Models
Århus. Work package 4. June 2001.

J. Díaz, M. Serna and D. M. Thilikos
The Complexity of Parameterized H-Colorings: A survey
Barcelona. Work package 4. June 2001.

J. Díaz, M. Serna and D. M. Thilikos
Counting H-colorings of Partial k-trees
Barcelona. Work package 4. June 2001.

Rasmus Pagh and Jakob Pagter
Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting
Århus. Work package 4. June 2001.

J. Díaz, J. Petit and M. Serna
Faulty random geometric networks
Barcelona. Work package 2. June 2001.

A. Stewart, M. Clint, J. Gabarró and M. Serna
Towards refining BSP programs into loosely coupled distributed systems
Barcelona. Work package 4. June 2001.

J. Petit
Hamiltonian cycles in faulty random geometric networks
Barcelona. Work package 2. June 2001.

C. Àlvarez, R. Cases, J. Díaz, J. Petit and M. Serna
Communication tree problems
Barcelona. Work package 2. June 2001.

J. Díaz, J. Petit and M. Serna
A survey on graph layout problems
Barcelona. Work packages 2, 4 and 5. June 2001.

J. Díaz, M. Serna and D.M. Thilikós
Counting List H-Colorings and Variants
Barcelona. Work package 4. June 2001.

Michael Wand, Matthias Fischer, Ingmar Peter, Friedhelm Meyer auf der Heide and Wolfgang Straßer
The Randomized z-Buffer Algorithm: Interactive Rendering of Highly Complex Scenes
Paderborn. Work package 5. May 2001.

Artur Czumaj and Christian Sohler
Testing Hypergraph Coloring
Paderborn. Work package 4. May 2001.

Artur Czumaj and Christian Sohler
Soft Kinetic Data Structures
Paderborn. Work package 4. May 2001.

Gerth Stølting Brodal, Rolf Fagerberg and Christian N. S. Pedersen
Computing the Quartet Distance Between Evolutionary Trees in Time O(nlog² n)
Århus. Work package 4. May 2001.

Gerth Stølting Brodal, Rolf Fagerberg, Christian N. S. Pedersen and Anna Östlin
The Complexity of Constructing Evolutionary Trees Using Experiments
Århus. Work package 4. May 2001.

Hans L. Bodlaender, Richard B. Tan and Jan van Leeuwen
Finding a Delta-regular Supergraph of Minimum Order
Utrecht. Work package 2. May 2001.

Rolf Fagerberg, Rune E. Jensen and Kim S. Larsen
Search Trees with Relaxed Balance and Near-Optimal Height
Århus. Work package 4. May 2001.

Piotr Krysta and Anil Kumar
Approximation Algorithms for Minimum Size 2-Connectivity Problems
MPI. Work packages 2 and 4. May 2001.

Rasmus Pagh and Flemming Friche Rodler
Lossy Dictionaries
Århus. Work package 4. May 2001.

Marjan van den Akker, Han Hoogeveen and Steef van de Velde
Combining column generation and Lagrangean relaxation to solve a single-machine common due date problem
Utrecht. Work packages 3 and 4. May 2001.

Rasmus Pagh and Flemming Friche Rodler
Cuckoo Hashing
Århus. Work packages 4 and 5. May 2001.

Christoph Buchheim and Michael Jünger
Detecting Symmetries by Branch & Cut
Cologne. Work package 4. May 2001.

Sixiang Hou and Han Hoogeveen
The three-machine proportionate flow shop problem with unequal machine speeds
Utrecht. Work package 3. May 2001.

Hans L. Bodlaender, Michael J. Dinneen and Bakhadyr Khoussainov
Relaxed Update and Partition Network Games
Utrecht. Work package 2. May 2001.

Marios Mavronicolas and Paul Spirakis
The Price of Selfish Routing
Patras. Work packages 2 and 4. May 2001.

Ioannis Chatzigiannakis, Sotiris Nikoletseas, Nearchos Paspallis, Paul Spirakis and Christos Zaroliagis
An Experimental Study of Basic Communication Protocols in Ad-Hoc Mobile Networks
Patras. Work packages 2 and 5. May 2001.

J. Díaz, D. Koukopoulos, S. Nikoletseas, M. Serna, P. Spirakis and D. Thilikos
Stability and non-stability of the FIFO Protocol
Barcelona and Patras. Work packages 2 and 4. May 2001.

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
An Efficient Communication Strategy for Ad-hoc Mobile Networks
Patras. Work packages 2 and 4. May 2001.

Burkhard Monien and Robert Preis
Upper Bounds on the Bisection Width of 3- and 4-regular Graphs
Paderborn. Work package 2. May 2001.

Dimitrios M. Thilikos, Maria J. Serna and Hans L. Bodlaender
A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth
Barcelona and Utrecht. Work package 4. May 2001.

Dimitrios M. Thilikos, Maria J. Serna and Hans L. Bodlaender
A constructive linear time algorithm for small cutwidth
Barcelona and Utrecht. Work package 4. May 2001.

Hans L. Bodlaender
Necessary edges in k-chordalizations of graphs
Utrecht. Work package 4. May 2001.

Jochen Alber, Hans L. Bodlaender, Henning Fernau and Rolf Niedermeier
Fixed Parameter Algorithms for Planar Dominating Set and Related Problems
Utrecht. Work package 4. May 2001.

Hans L. Bodlaender
A generic NP-hardness proof for a variant of Graph Coloring
Utrecht. Work package 4. May 2001.

Frédéric Chyzak
Algorithms Seminar, 1999-2000
INRIA. Work package 4. May 2001.

Dimitris Fotakis, Sotiris Nikoletseas, Vicky Papadopoulou and Paul Spirakis
NP-completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs
Patras. Work packages 2 and 4. May 2001.

Dimitris Fotakis, Sotiris Nikoletseas, Vicky Papadopoulou and Paul Spirakis
Hardness Results and Efficient Approximations for Frequency Assignment Problems: Radio Labelling and Radio Coloring
Patras. Work packages 2 and 4. May 2001.

Dimitris Fotakis, Sotiris Nikoletseas, Vicky Papadopoulou and Paul Spirakis
Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies
Patras. Work packages 2 and 4. May 2001.

Han Hoogeveen and Gerhard J. Woeginger
Some comments on sequencing with controllable processing times
Utrecht. Work package 3. May 2001.

Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc and Yannis C. Stamatiou
Locating Information with Uncertainty in Fully Interconnected Networks: The Case of Non-Distributed Memory
Patras. Work package 2. May 2001.

Alexis C. Kaporis, Lefteris M. Kirousis and Yannis C. Stamatiou
A note on the non-colorability threshold of a random graph
Patras. Work package 4. May 2001.

Alexis Kaporis, Lefteris Kirousis, Yannis Stamatiou, Malvina Vamvakari and Michele Zito
The unsatisfiability threshold revisited
Patras. Work package 4. May 2001.

Daniele Frigioni, Tobias Miller, Umberto Nanni and Christos Zaroliagis
An Experimental Study of Dynamic Algorithms for Transitive Closure
Patras and Rome. Work package 5. May 2001.

Sotiris Nikoletseas, Grigorios Prasinos, Paul Spirakis and Christos Zaroliagis
Attack Propagation in Networks
Patras. Work packages 2 and 5. May 2001.

Meinolf Sellmann and Torsten Fahle
CP-based Lagrangian Relaxation for a Multimedia Application
Paderborn. Work packages 2 and 4. May 2001.

Peter Sanders
Asynchronous Scheduling of Redundant Disk Arrays
MPI. Work packages 1, 2 and 5. May 2001.

Ulrich Meyer
Directed Single-Source Shortest-Paths in Linear Average-Case Time
MPI. Work packages 2 and 4. May 2001.

Rajmohan Rajaraman, Andréa W. Richa, Berthold Vöcking and Gayathri Vuppuluri
A Data Tracking Scheme for General Networks
MPI. Work packages 1, 2 and 4. May 2001.

Ulrich Meyer
External Memory BFS on Undirected Graphs with Bounded Degree
MPI. Work package 1. May 2001.

Ulrich Meyer and Peter Sanders
Parallel Shortest Path for Arbitrary Graphs
MPI. Work packages 1 and 2. May 2001.

Ulrich Meyer
Heaps are better than Buckets: Parallel Shortest Paths on unbalanced Graphs
MPI. Work packages 1 and 2. May 2001.

Lars Arge, Ulrich Meyer, Laura Toma and Norbert Zeh
On External-Memory Planar Depth First Search
MPI. Work packages 1, 2 and 4. May 2001.

José L. Balcázar, Yang Dai and Osamu Watanabe
Random sampling techniques for training support vector machines
Barcelona. Work package 1. May 2001.

Torsten Fahle, Ulrich Junker, Stefan E. Karisch, Niklas Kohl, Meinolf Sellmann and Bo Vaaben
Constraint Programming Based Column Generation for Crew Assignment
Paderborn. Work packages 3 and 4. May 2001.

Meinolf Sellmann, Kyriakos Zervoudakis, Panagiotis Stamatopoulos and Torsten Fahle
Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search
Paderborn. Work packages 3 and 4. May 2001.

Robert Elsässer, Thomas Lücking and Burkhard Monien
New Spectral Bounds on k-Partitioning of Graphs
Paderborn. Work package 2. May 2001.

Norbert Sensen
Lower Bounds and Exact Algorithms for the Graph Partitioning Problem using Multicommodity Flows
Paderborn. Work package 2. May 2001.

Meinolf Sellmann and Torsten Fahle
Coupling Variable Fixing Algorithms for the Automatic Recording Problem
Paderborn. Work package 2. May 2001.

Robert Elsässer, Rastislav Královic and Burkhard Monien
Scalable Sparse Topologies with Small Spectrum
Paderborn. Work package 2. May 2001.

Spyros Kontogiannis, Grammati Pantziou, Paul Spirakis and Moti Yung
Robust parallel computations through randomization
Patras and MPI. Work packages 2 and 4. May 2001.

Matthias Elf, Michael Jünger and Giovanni Rinaldi
Minimizing Breaks by Maximizing Cuts
Cologne. Work package 4. May 2001.

Peter Sanders
Fast Priority Queues for Cached Memory
MPI. Work packages 1 and 5. May 2001.

Peter Sanders
Reconciling Simplicity and Realism in Parallel Disk Models
MPI. Work package 1. May 2001.

Peter Sanders
Presenting Data from Experiments in Algorithmics
MPI. Work package 5. May 2001.

Catherine Mc Geoch, Peter Sanders, Rudolf Fleischer, Paul R. Cohen and Doina Precup
Searching for Big-Oh in the Data: Inferring Asymptotic Complexity from Experiments
MPI. Work package 5. May 2001.

David A. Hutchinson, Peter Sanders and Jeffrey S. Vitter
Duality between prefetching and queued writing with Parallel Disks
MPI. Work packages 1 and 4. May 2001.

Lars Jacobsen, Kim S. Larsen and Morten N. Nielsen
On the Existence and Construction of Non-Extreme (a,b)-Trees
Århus. Work packages 1 and 4. May 2001.

Panagiota Fatourou
Low-Contention Depth-First Scheduling of Parallel Computations with Write-Once Synchronization Variables
MPI. Work package 2. May 2001.

Panagiota Fatourou and Maurice Herlihy
Brief Announcement: Adding Networks
MPI. Work package 2. May 2001.

Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren and Sven Thiel
An Efficient Algorithm for the Configuration Problem of Dominance Graphs
MPI. Work package 2. May 2001.

Stefan Burkhardt and Juha Kärkkäinen
Better Filtering with Gapped q-Grams
MPI. Work packages 1, 4 and 5. May 2001.

Andreas Crauser
LEDA-SM:External Memory Algorithms and Data Structures in Theory and Practice
MPI. Work packages 1 and 5. May 2001.

Petra Berenbrink, Tom Friedetzky and Leslie Ann Goldberg
The Natural Work-Stealing Algorithm is Stable
Warwick. Work packages 1, 2 and 4. May 2001.

Christof Krick, Harald Räcke and Matthias Westermann
Approximation Algorithms for Data Management in Networks
Paderborn. Work packages 2 and 4. May 2001.

Ben H.H. Juurlink, Petr Kolman, Friedhelm Meyer auf der Heide and Ingo Rieping
Optimal Broadcast on Parallel Locality Models
Paderborn. Work package 2. May 2001.

André Brinkmann, Kay Salzwedel and Christian Scheideler
Efficient, Distributed Data Placement Strategies for Storage Area Networks
Paderborn. Work packages 1 and 2. May 2001.

Rasmus Pagh
A Trade-Off For Worst-Case Efficient Dictionaries
Århus. Work package 4. May 2001.

Rasmus Pagh
On the Cell Probe Complexity of Membership and Perfect Hashing
Århus. Work package 4. May 2001.

Sotiris Nikoletseas and Paul Spirakis
Randomized Techniques for Modelling Faults and Achieving Robust Computing
Patras. Work packages 2 and 4. May 2001.

Sotiris Nikoletseas and Paul Spirakis
Efficient Communication Establishment in Adverse Communication Environments
Patras. Work package 2. May 2001.

John Garofalakis, Sotiris Nikoletseas and Paul Spirakis
Latency Lower Bounds for Randomized Dynamic Bandwidth Allocation
Patras. Work packages 2 and 4. May 2001.

Sotiris Nikoletseas, Krishna Palem, Paul Spirakis and Moti Yung
Connectivity Properties in Random Regular Graphs with Edge Faults
Patras. Work packages 2 and 4. May 2001.

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
An Efficient Routing Protocol for Hierarchical Ad-hoc Mobile Networks
Patras. Work packages 2 and 5. May 2001.

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
Analysis and Experimental Evaluation of an Innovative and Efficient Routing Protocol for Ad-hoc Mobile Networks
Patras. Work packages 2 and 5. May 2001.

Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou
Efficient On-line Communication in Cellular Networks
Patras. Work package 2. May 2001.

Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis and Pino Persiano
Randomized Path Coloring on Binary Trees
Patras. Work packages 2 and 4. May 2001.

Constantinos Bartzis, Ioannis Caragiannis, Christos Kaklamanis and Ioannis Vergados
Experimental Evaluation of Hot-Potato Routing Algorithms in 2-Dimensional Processor Arrays
Patras. Work packages 2 and 5. May 2001.

Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou
Competitive Analysis of On-line Randomized Call Control in Cellular Networks
Patras. Work package 2. May 2001.

Ioannis Caragiannis, Christos Kaklamanis and Ioannis Vergados
Greedy Dynamic Hot-Potato Routing on Arrays
Patras. Work packages 2 and 5. May 2001.

Ioannis Caragiannis, Christos Kaklamanis and Pino Persiano
Wavelength Routing in All-Optical Tree Networks: A Survey
Patras. Work packages 2 and 4. May 2001.

Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes and Herve Rivano
Fractional Path Coloring with Applications to WDM Networks
Patras. Work package 2. May 2001.

Stephen Alstrup, Gerth Stølting Brodal and Theis Rauhe
Optimal Static Range Reporting in One Dimension
Århus. Work package 4. May 2001.

Lars Jacobsen and Kim S. Larsen
Variants of (a,b)-Trees with Relaxed Balance
Århus. Work packages 1, 4 and 5. May 2001.

Kim S. Larsen
Relaxed Multi-Way Trees with Group Updates
Århus. Work packages 1 and 4. May 2001.

Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen and Morten N. Nielsen
Fair versus Unrestricted Bin Packing
Århus. Work package 4. May 2001.

Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, Guo-Hui Lin and Rob van Stee
Tight Bounds on the Competitive Ratio on Accommodating Sequences
Århus. Work packages 3 and 4. May 2001.

Friedhelm Meyer auf der Heide, Harald Räcke and Matthias Westermann
Data Management in Hierarchical Bus Networks
Paderborn. Work packages 2 and 4. April 2001.

Stefano Leonardi, Alberto Marchetti-Spaccamela and Andrea Vitaletti
Approximation algorithms for bandwidth and storage allocation under real time constraints
Rome. Work package 2. April 2001.

Luca Becchetti and Stefano Leonardi
Non-Clairvoyant Scheduling to Minimize the Average Flow Time on Single and Parallel Machines
Rome. Work package 2. April 2001.

L. Becchetti, S. Leonardi and M. Muthukrishnan
Average Stretch without Migration
Rome. Work package 2. April 2001.

Christine Fricker, Philippe Robert and Danielle Tibi
On the fluid limits of some loss networks
INRIA. Work packages 2 and 4. April 2001.

Philippe Flajolet, Yves Guivarc'h, Wojciech Szpankowski and Brigitte Vallée
Hidden Pattern Statistics
INRIA. Work packages 1 and 4. April 2001.

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela and Kirk Pruhs
Online Weighted Flow Time and Deadline Scheduling
Rome. Work package 4. April 2001.

Massimiliano Curcio, Stefano Leonardi and Andrea Vitaletti
Integrated Prefetching and Caching for the World Wide Web via User Cooperation
Rome. Work package 2. April 2001.

Giuseppe Cattaneo, Umberto Ferraro-Petrillo and Giuseppe F. Italiano
CATAI: Concurrent Algorithms and data Types Animationover the Internet
Rome. Work package 5. April 2001.

J. Baixeries, G. Casas-Garriga and J.L. Balcázar
A Faster Algorithm for Finding Frequent Sets
Barcelona. Work package 1. April 2001.

Lars Arge, Gerth Stølting Brodal and Laura Toma
On External-Memory MST, SSSP and Multi-way Planar Graph Separation
Århus. Work packages 1 and 4. April 2001.

K. Meer and G.W. Weber
Some aspects of studying an optimization or decision problem in different computational models
Århus. Work package 4. April 2001.

J.A. Makowsky and K. Meer
Polynomials of bounded tree-width
Århus. Work package 4. April 2001.

Stephen Alstrup, Gerth Stølting Brodal and Theis Rauhe
New Data Structures for Orthogonal Range Searching
Århus. Work package 4. April 2001.

Gerth Stølting Brodal and Riko Jacob
Dynamic Planar Convex Hull with Optimal Query Time and O(log nloglog n) Update Time
Århus. Work package 4. April 2001.

Vincent Dumas, Fabrice Guillemin and Philippe Robert
Limit results for Markovian models of TCP
INRIA. Work package 2. April 2001.

Serafino Cicerone, Gabriele Di Stefano, Daniele Frigioni and Umberto Nanni
A Fully Dynamic Algorithm for Distributed Shortest Paths
Rome. Work packages 2 and 4. March 2001.

Daniele Frigioni, Alberto Marchetti-Spaccamela and Umberto Nanni
Fully Dynamic Shortest Paths in Digraphs with Arbitrary Arc Weights
Rome. Work packages 2 and 4. March 2001.

Michele Flammini and Gaia Nicosia
On Multicriteria Online Problems
Rome. Work package 4. March 2001.

Alberto Caprara, Giuseppe F. Italiano, G. Mohan, Alessandro Panconesi and Aravind Srinivasan
Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem
Rome. Work packages 2 and 4. March 2001.

Massimiliano Caramia, Paolo Dell'Olmo and Giuseppe F. Italiano
CHECKCOL: Improved Local Search for Graph Coloring
Rome. Work package 5. March 2001.

Massimiliano Caramia, Paolo Dell'Olmo and Giuseppe F. Italiano
New Algorithms for Examination Timetabling
Rome. Work package 5. March 2001.

C. Demetrescu and I. Finocchi
Smooth Animation of Algorithms in a Declarative Framework
Rome. Work package 5. March 2001.

C. Demetrescu and G.F. Italiano
Fully Dynamic Transitive Closure: Breaking Through the O(n²) Barrier
Rome. Work package 2. March 2001.

C. Demetrescu and G.F. Italiano
What Do We Learn from Experimental Algorithmics?
Rome. Work package 5. March 2001.

C. Demetrescu, D. Frigioni, A. Marchetti-Spaccamela and U. Nanni
Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study
Rome. Work package 5. March 2001.

C. Demetrescu, I. Finocchi and G. Liotta
Visualizing Algorithms over the Web with the Publication-driven Approach
Rome. Work package 5. March 2001.

José Luis Balcázar, Jorge Castro and David Guijarro
A General Dimension for Exact Learning
Barcelona. Work package 1. March 2001.

Cyril Banderier, Philippe Flajolet, Gilles Schaeffer and Michele Soria
Random Maps, Coalescing Saddles, Singularity Analysis, and Airy Phenomena
INRIA. Work packages 4 and 5. March 2001.

Giorgio Ausiello, Paolo G. Franciosa, Daniele Frigioni and Roberto Giaccio
Decremental Maintenance of Minimum Rank Hyperpaths and Minimum Models of Horn Formulae
Rome. Work package 4. February 2001.

Kurt Mehlhorn and Guido Schäfer
A Heuristic for Dijkstra's Algorithm with Many Targets and its Use in Weighted Matching Algorithms
MPI. Work packages 4 and 5. February 2001.

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps
Generating functions for generating trees
INRIA. Work package 4. February 2001.

Alain Dupuis, Fabrice Guillemin and Philippe Robert
Modeling Max-Min Fairness for Elastic Flows in Telecommunication Networks
INRIA. Work package 2. February 2001.

Philippe Flajolet and Guy Louchard
Analytic Variations on the Airy Distribution
INRIA. Work package 4. February 2001.

Alexandre Tiskin
Parallel convex hull computation by generalised regular sampling
Warwick. Work packages 1 and 4. February 2001.

Kurt Mehlhorn and Mark Ziegelmann
CNOP - A Package for Constrained Network Optimization
MPI. Work packages 2, 3 and 4. February 2001.

P. Sanders and R. Solis-Oba
How Helpers Hasten h-Relations
MPI. Work packages 1, 2 and 4. January 2001.

Philippe Flajolet, Kostas Hatzis, Sotiris Nikoletseas and Paul Spirakis
On the Robustness of Interconnections in Random Graphs:A Symbolic Approach
INRIA and Patras. Work packages 2 and 4. January 2001.

Jean-Francois Dantzer and Philippe Robert
Analysis of a multi-class queueing system
INRIA. Work packages 2 and 4. January 2001.

M. Adler, F. Fich, L. A. Goldberg and M. Paterson
Tight Size Bounds for Packet Headers in Narrow Meshes
Warwick. Work package 2. January 2001.

Philippe Flajolet and Robert Sedgewick
Analytic Combinatorics: Functional Equations, Rational and Algebraic Functions
INRIA. Work package 4. January 2001.

L.A. Goldberg, M. Jerrum, S. Kannan and M. Paterson
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols
Warwick. Work packages 2 and 4. January 2001.

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum
On the relative complexity of approximate counting problems
Warwick. Work package 4. January 2001.

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Gabriel Istrate and Mark Jerrum
Convergence of the Iterated Prisoner's Dilemma Game
Warwick. Work package 4. January 2001.

Leslie Ann Goldberg
Computation in permutation groups: counting and randomly sampling orbits
Warwick. Work package 4. January 2001.

Alexandre Tiskin
A new way to divide and conquer
Warwick. Work packages 1 and 4. January 2001.

Philippe Flajolet, Xavier Gourdon and Daniel Panario
The complete analysis of a polynomial factorization algorithm over finite fields
INRIA. Work package 4. January 2001.

Philippe Flajolet and Brigitte Vallée
Continued Fractions, Comparison Algorithms, and Fine Structure Constants
INRIA. Work packages 4 and 5. January 2001.