list accepted papers for ICALP 2003
icalp2003 at TUE.nl
icalp2003 at TUE.nl
Wed Mar 19 14:36:56 PST 2003
-------------------------------------------------------------------------
We apologize for the reception of multiple copies of this message.
----------------------------------------------------------------------------
----------------------------
============================================================================
==========
List of papers accepted for ICALP'2003, Track A and Track B
Eindhoven, The Netherlands, June 30 - July 4, 2003
http://www.win.tue.nl/icalp2003/
============================================================================
==========
Vincent Blondel, Paul Van Dooren
Similarity matrices for pairs of graphs
Arnold Schoenhage
Adaptive raising strategies optimizing relative efficiency
Sergei Bespamyatnikh, Michael Segal
Dynamic algorithms for approximating interdistances
Amos Korman, David Peleg
Labeling schemes for dynamic tree networks
Geraud Senizergues
The equivalence problem for t-turn DPDA is co-NP
John Hitchcock, Jack Lutz, Elvira Mayordomo
Scaled dimension and nonuniform complexity
Yossi Matias, Ely Porat
Efficient pebbling for list traversal synopses
Alexander Ageev, Yinyu Ye, Jiawei Zhang
Improved combinatorial approximation algorithms for the k-level facility
location problem
Markus Blaeser
An improved approximation algorithm for the asymmetric TSP with strengthened
triangle inequality
Susanne Albers, Rob van Stee
A study of integrated document and connection caching
Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat
Function matching: algorithms, applications, and a lower bound
Eyal Even-Dar, Alex Kesselman, Yishay Mansour
Convergence time to Nash equilibria
Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani
MAX k-CUT and approximating the chromatic number of random graphs
Jiri Fiala, Daniel Paulusma
The computational complexity of the role assignment problem
Vipul Bansal, Aseem Agrawal, Varun Malhotra
Stable marriages with multiple partners: efficient search for an optimal
solution
Juraj Hromkovic, Georg Schnitger
Pushdown automata and multicounter machines, a comparison of computation
mode
Jens Jaegerskuepper
Analysis of a simple evolutionary algorithm for minimization in Euclidean
spaces
Noam Berger, Bela Bollobas, Christian Borgs, Jennifer Chayes, Oliver Riordan
Degree distribution of the FKP network model
Luisa Gargano, Mikael Hammar
There are spanning spiders in dense graphs (and we know how to find them)
Annalisa De Bonis, Leszek Gasieniec, Ugo Vaccaro
Generalized framework for selectors with applications in optimal group
testing
Michael Elkin, Guy Kortsarz
Approximation algorithm for the directed telephone multicast problem
Sanjeev Arora, Kevin Chang
Approximation schemes for degree-restricted MST and red-blue separation
problem
Surender Baswana, Sandeep Sen
A simple linear time algorithm for computing a (2k-1)-Spanner of
O(n^{1+1/k}) size in weighted graphs
Chandra Chekuri, Marcelo Mydlarz, Bruce Shepherd
Multicommodity demand flow in a tree
Randeep Bhatia, Julia Chuzhoy, Ari Freund, Joseph Naor
Algorithmic aspects of bandwidth trading
Chandra Chekuri, Sudipto Guha, Joseph Naor
Approximating Steiner k-cuts
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa
Makino
An intersection inequality for discrete distributions and related generation
problems
Erik Demaine, Fedor Fomin, MohammadTaghi Hajiaghayi, Dimitrios Thilikos
Fixed-parameter algorithms for the (k,r)-center in planar graphs and map
graphs
Gianni Franceschini, Roberto Grossi
Optimal cache-oblivious implicit dictionaries
Anna Gal, Peter Bro Miltersen
The cell probe complexity of succinct data structures,
Alex Hall, Steffen Hippler, Martin Skutella
Multicommodity flows over time: efficient algorithms and complexity
Rene Sitters, Leen Stougie, Willem Paepe
A competitive algorithm for the general 2-server problem
Luis Antunes, Lance Fortnow
Sophistication revisited
Peter Hoyer, Michele Mosca, Ronald de Wolf
Quantum search on bounded-error inputs
Dimitris Fotakis
On the competitive ratio for online facility location
Satoshi Ikeda, Izumi Izumi Kubo, Norihiro Okumoto, Masafumi Yamashita
Impact of local topological information on random walks on finite graphs
Pilu Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna, Walter Unger
On-line load balancing made simple: greedy strikes back
Seffi Naor, Hadas Shachnai, Tami Tamir
Real-time scheduling with a budget
Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro
Solving the robots gathering problem
Rainer Feldmann, Martin Gairing, Thomas Luecking, Burkhard Monien, Manuel
Rode
Nashification and the coordination ratio for a selfish routing game
Brian Dean, Michel Goemans
Improved approximation algorithms for minimum-space advertisement scheduling
Baruch Awerbuch, Andre Brinkmann, Christian Scheideler
Anycasting in adversarial systems: routing and admission control
Jianer Chen, Iyad Kanj, Ljubomir Perkovic, Eric Sedgwick, Ge Xia
Genus characterizes the complexity of graph problems: some tight results
Markus Holzer, Martin Kutrib
Flip-pushdown automata: k+1 pushdown reversals are better than k
Manuel Bodirsky, Clemens Gröpl, Mihyun Kang
Generating labeled planar graphs uniformly at random
Rajiv Gandhi, Eran Halperin, Samir Khuller, Guy Kortsarz, Aravind Srinivasan
An improved approximation algorithm for vertex cover with hard capacities
Dominique Poulalhon, Gilles Schaeffer
Optimal coding and sampling of triangulations
Ian Munro, Rajeev Raman, Venkatesh Raman, Srinivasa Rao Satti
Succinct representations of permutations
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
A direct sum theorem in communication complexity via message compression
Rajeev Raman, Srinivasa Rao
Succinct dynamic dictionaries and trees
Daniel Bleichenbacher, Aggelos Kiayias, Moti Yung
Decoding of interleaved Reed Solomon codes over noisy data,
Juha Kärkkäinen, Peter Sanders
Simple linear work suffix array construction
Manfred Droste, Dietrich Kuske
Skew and infinitary formal power series
Ernst-Erich Doberkat
Semi-pullbacks and bisimulations in categories of stochastic relations
Stefan Blom, Wan Fokkink, Sumit Nain
On the axiomatizability of ready traces, ready simulation and failure traces
Juraj Hromkovic, Georg Schnitger
Nondeterminisn versus determinism for two-way finite automata:
generalizations of Sipser's separation
Daniele Gorla, Rosario Pugliese
Resource access and mobility control with dynamic privileges acquisition
Jan Johannsen, Martin Lange
CTL+ is complete for double exponential time
Davide Ancona, Sonia Fagorzi, Eugenio Moggi, Elena Zucca
Mixin modules and computational effects
Thierry Cachat
Higher order pushdown automata, the Caucal hierarchy of graphs and parity
games
Gaoyan Xie, Zhe Dang, Oscar Ibarra
A solvable class of quadratic Diophantine equations with applications to
verification of infinite state systems
Alexander Okhotin
Decision problems for language equations with Boolean operations
Roberto Bruni, Jose Meseguer
Generalized rewrite theories
Salvatore La Torre, Margherita Napoli, Mimmo Parente, Gennaro Parlato
Hierarchical and recursive state machines with context-dependent properties
Cindy Eisner, Dana Fisman, John Havlicek, Anthony McIsaac, David Van
Campenhout
The definition of a temporal clock operator
Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro
Replication vs. recursive definitions in channel based calculi
Richard Mayr
Undecidability of weak bisimulation equivalence for 1-counter processes
Felix Klaedtke, Harald Ruess
Monadic second-order logics with cardinalities
Orna Kupferman, Moshe Vardi
Pi_2 intersected Sigma_2 equals AFMC
Alexander Rabinovich
Quantitative analysis of probabilistic lossy channel systems
Massimo Merro, Francesco Zappa Nardelli
Bisimulation proof methods for mobile ambients
Tatiana Rybina, Andrei Voronkov
Upper bounds for a theory of queues
Zena Ariola, Hugo Herbelin
Minimal classical logic and control operators
Arnaud Carayol, Thomas Colcombet
On equivalent representations of infinite structures
Philippe Schnoebelen
Oracle circuits for branching-time model checking
Luca de Alfaro, Thomas A. Henzinger, Rupak Majumdar
Discounting the future in systems theory
Thomas Henzinger, Ranjit Jhala, Rupak Majumdar
Counterexample guided control
Jo Hannay
Axiomatic criteria for quotients and subobjects for higher-order data types
Francois Denis, Yann Esposito
Residual languages and probabilistic automata
Francisco Gutierrez, Blas Ruiz
Expansion postponement via cut elimination in sequent calculi for pure type
systems
Michele Bugliesi, Silvia Crafa, Amela Prelic, Vladimiro Sassone
Secrecy in untrusted networks
Luca de Alfaro, Marco Faella
Information flow in concurrent games
Marielle Stoelinga , Frits Vaandrager
A testing scenario for probabilistic automata
Arkadev Chattopadhyay, Denis Therien
Locally commutative categories
============================================================================
==========
-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce
mailing list