LATIN 2008
| The Online Transportation Problem: On the Exponential Boost of One Extra Server |
Christine Chung and Kirk Pruhs and Patchrawat Uthaisombut
Affiliations: University of Pittsburgh
| Simpler constant-seed condensers |
Domingos Dellamonica Jr.
Affiliations: Emory University
| Fully-Compressed Suffix Trees |
Luís M. S. Russo and Gonzalo Navarro and Arlindo L. Oliveira
Affiliations: INESC-ID and University of Chile
| Average Rate Speed Scaling |
Nikhil Bansal and David Bunde and Ho-Leung Chan and Kirk Pruhs
Affiliations: IBM and Knox College and University of Pittsburgh and University of Pittsburgh
| Improved Dynamic Rank-Select Entropy-Bound Structures |
Rodrigo González and Gonzalo Navarro
Affiliations: Dept. of Computer Science, University of Chile.
| Approximate polynomial gcd: small degree and small height perturbations |
Joachim von zur Gathen and Igor E. Shparlinski
Affiliations: University of Bonn and Macquarie University
| Competitive Investment with Economies of Scale |
Martin Hoefer
Affiliations: Universität Konstanz
| On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints |
Gerard Cornuejols and Francois Margot
Affiliations: Carnegie Mellon University
| Emergency connectivity in ad-hoc networks with selfish nodes |
George Karakostas and Euripides Markou
Affiliations: Department of Computing & Software and School of Computational Engineering & Science, McMaster University
| Approximating Steiner Networks with Node Weights |
Zeev Nutov
Affiliations: The Open University of Israel
| Approximating Minimum-Power Degree and Connectivity Problems |
Guy Kortsarz and Vahab S. Mirrokni and Zeev Nutov and Elena Tsanko
Affiliations: The Open University of Israel
| Minimum Cost Homomorphisms to Reflexive Digraphs |
Arvind Gupta , Pavol Hell, Mehdi Karimi, Arash Rafiey
Affiliations: School of Computing Science, Simon Fraser University
| New Upper Bound on Vertex Folkman Numbers |
Andrzej Dudek and Vojtech Rodl
Affiliations: Emory University
| Pseudorandom Graphs from Elliptic Curves |
Igor E. Shparlinski
Affiliations: Macquarie University
| On the Complexity of Reconstructing H-free Graphs from their Star Systems |
Fedor V. Fomin and Jan Kratochv and Daniel Lokshtanov and Federico Mancini and Jan Arne Telle
Affiliations: Univeristy of Bergen and Charles University
| Computing the growth of the number of overlap-free words with spectra of matrices |
Raphaël M. Jungers and Vladimir Protasov and Vincent D. Blondel
Affiliations: Université catholique de Louvain, Moscow State University,Université catholique de Louvain
| An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups |
Gabor Ivanyos and Luc Sanselme and Miklos Santha
Affiliations: LRI and Sztaki
| Optimal Higher Order Delaunay Triangulations of Polygons |
Rodrigo I. Silveira and Marc van Kreveld
Affiliations: Utrecht University
| The Generalized Median Stable Matchings: finding them is not that easy |
Christine T. Cheng
Affiliations: University of Wisconsin-Milwaukee
| Origami embedding of piecewise-linear two-manifolds |
Marshall Bern and Barry Hayes
Affiliations: Palo Alto Research Center and Google, Inc.
| Sorting and Selection with Random Costs |
Stanislav Angelov and Keshav Kunal and Andrew McGregor
Affiliations: UPenn and UPenn and UCSD
| Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes |
J. Czyzowicz and S. Dobrev and T. Fevens and H. González-Aguilar and E. Kranakis and J. Opatrny and J. Urrutia
Affiliations: Université du Québec en Outaouais; University of Ottawa; Centro de Investigacion en Matematicas, Guanajuato; Concordia University; Carleton University; Instituto de Matemáticas, México
| Optimization and recognition for $K_5$-minor free graphs in linear time |
Bruce Reed and Zhentao Li
Affiliations: CNRS and McGill University, McGill Universiy
| Stateless Near Optimal Flow Control with Poly-logarithmic Convergence |
Baruch Awerbuch and Rohit Khandekar
Affiliations: Johns Hopkins University and IBM T. J. Watson Research Center
| The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences |
Richard Matthew McCutchen
Affiliations: University of Maryland
| On Stateless Multihead Automata: Hierarchies and the Emptiness Problem |
Oscar H. Ibarra and Juhani Karhumaki and Alexander Okhotin
Affiliations: Department of Computer Science, Unviversity of California - Santa Barbara; Department of Mathematics, University of Turku
| Bandwidth of bipartite permutation graphs in polynomial time |
Pinar Heggernes and Dieter Kratsch and Daniel Meister
Affiliations: University of Bergen, Norway (first and last author), University of Metz, France (middle author)
| Random 2-XORSAT at the satisfiability threshold |
Vlady Ravelomanana and Herve Daudé
Affiliations: LIPN-UMR7030, Université de Paris Nord and LATP-UMR6632, Université de Provence
| On Injective Colourings of Chordal Graphs |
Pavol Hell and Andre Raspaud and Juraj Stacho
Affiliations: Simon Fraser University; LaBRI Universite Bordeaux I
| Spanners of Complete k-Partite Geometric Graphs |
Prosenjit Bose and Paz Carmi and Mathieu Couture and Anil Maheshwari and Pat Morin and Michiel Smid
Affiliations: School of Computer Science, Carleton University, Ottawa, Canada
| Energy Efficient Monitoring in Sensor Networks |
Amol Deshpande and Samir Khuller and Azarakhsh Malekian and Mohammed Toossi
Affiliations: University of Maryland
| Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms |
Paul Bonsma and Florian Zickfeld
Affiliations: Technische Universitaet Berlin
| A New Algorithm for Nearest Neighbor Search using Kd-trees |
Rina Panigrahy
Affiliations: Microsoft Research
| Parallel Repetition of the Odd Cycle Game |
Kooshiar Azimian and Mario Szegedy
Affiliations: Rutgers University
| Sparse Solutions to Semidefinite Programs |
Elad Hazan
Affiliations: IBM Research
| Ptolemaic Graphs and Interval Graphs are Leaf Powers |
Andreas Brandstadt and Christian Hundt
Affiliations: University of Rostock, Computer Science Department
| Maximizing the minimum load for selfish agents |
Leah Epstein and Rob van Stee
Affiliations: University of Haifa, Israel and Max Planck Institut für Informatik, Saarbrücken, Germany.
| On 2-Subcolourings of Chordal Graphs |
Juraj Stacho
Affiliations: Simon Fraser University
| Collective Tree Spanners of Homogeneously Orderable Graphs |
Feodor F. Dragan and Chenyu Yan and Yang Xiang
Affiliations: Kent State University
| Coloring Geometric Range Spaces |
Greg Aloupis and Jean Cardinal and Sebastien Collette and Stefan Langerman and Shakhar Smorodinsky
Affiliations: Universite Libre de Bruxelles, Belgium, and Hebrew University, Israel
| Fixed-Parameter Algorithms for Cluster Vertex Deletion |
Falk Hueffner and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier
Affiliations: Friedrich-Schiller-Universitaet Jena, Germany
| Paths and Trails in Edge-Colored Graphs |
A. Abouelaoualim and K. Ch. Das and L. Faria and Y. Manoussakis and C. Martinhon and R. Saad
Affiliations: Université Paris-Sud, Estadual University of Rio de Janeiro and Fluminense Federal University
| Randomized Rendezvous with Limited Memory |
Evangelos Kranakis and Danny Krizanc and Pat Morin
Affiliations: Carleton University and Wesleyan University
| Simplifying 3D Polygonal Chains Under the Discrete Frechet DIstance |
Sergey Bereg and Minghui Jiang and Wencheng Wang and Boting Yang and Binhai Zhu
Affiliations: Montana State University, University of Regina, University of Texas and Utah University
| Finding heavy hitters over the sliding window of a weighted data stream |
Regant Y.S. Hung and H.F. Ting
Affiliations: The University of Hong Kong
| Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers |
Marcin Bienkowski and Aleksander Mądry
Affiliations: Institute of Computer Science, University of Wroclaw and CSAIL, MIT
| Weighted Rectilinear Approximation of Points in the Plane |
Mario A. Lopez and Yan Mayster
Affiliations: University of Denver, Department of Computer Science
| How to Complete a Doubling Metric |
Anupam Gupta and Kunal Talwar
Affiliations: Carnegie Mellon University and Microsoft Research SVC
| Approximating Crossing Minimization in Radial Layouts |
Seok-Hee Hong and Hiroshi Nagamochi
Affiliations: University of Sydney and Kyoto University
| On dissemination thresholds in regular and irregular graph classes |
Ivan Rapaport and Karol Suchan and Ioan Todinca and Jacques Verstraete
Affiliations: Universidad de Chile, Santiago, Chile (I.R., K.S.), University of Orleans, Orleans, France (I.T.), University of California, San Diego, USA (J.V.)
| Guided Search and a Faster Deterministic Algorithm for 3-SAT |
Dominik Scheder
Affiliations: ETH Zurich
| Efficient approximation algorithms for shortest cycles in undirected graphs |
Andrzej Lingas and Eva-Marta Lundell
Affiliations: Department of Computer Science, Lund University, Lund, Sweden
| Comparing and Aggregating Partially Resolved Trees |
Mukul S. Bansal and Jianrong Dong and David Fernández-Baca
Affiliations: Department of Computer Science, Iowa State University, Ames, IA 50011, USA
| Quantum Property Testing of Group Solvability |
Yoshifumi Inui and Francois Le Gall
Affiliations: Univ. Tokyo / ERATO-SORST QCI project, JST
| A Representation Theorem for union-difference Families and Application |
B.-M. Bui Xuan and M. Habib
Affiliations: CNRS - LIRMM - Université Montpellier II France and CNRS - LIAFA - Université Paris Diderot France
| Domination in Geometric Intersection Graphs |
Thomas Erlebach and Erik Jan van Leeuwen
Affiliations: University of Leicester and CWI Amsterdam
| Myhill-Nerode Theorem for Recognizable Tree Series Revisited |
Andreas Maletti
Affiliations: International Computer Science Institute, Berkeley, USA
| List Update with Locality of Reference |
Spyros Angelopoulos and Reza Dorrigiv and Alejandro Lopez-Ortiz
Affiliations: University of Waterloo
| The View Selection Problem for Regular Path Queries |
Sergey Afonin
Affiliations: Moscow State University
| Algorithms to locate errors using covering arrays |
Conrado Martinez and Lucia Moura and Daniel Panario and Brett Stevens
Affiliations: Universitat Politecnica de Catalunya, University of Ottawa, Carleton University, Carleton University
| Paths with no small angles |
Imre Barany and Attila Por and Pavel Valtr
Affiliations: Rényi Institut and Charles University
| A polyhedral investigation of the LCS problem and a repetition-free variant |
Cristina G. Fernandes and Carlos E. Ferreira and Christian Tjandraatmadja and Yoshiko Wakabayashi
Affiliations: Universidade de São Paulo, Brazil
| Solving NP-Complete Problems with Quantum Search |
Martin Fürer
Affiliations: Pennsylvania State University
| I/O-Efficient Point Location in a Set of Rectangles |
Yakov Nekrich
Affiliations: University of Bonn
| Speeding-up Lattice Reduction with Random Projections |
A. Akhavi and D. Stehlé
Affiliations: Université de Caen and Université Paris 7, CNRS and École Normale Supérieure de Lyon,
| Approximation Algorithms for k-Hurdle Problems |
Brian C. Dean and Adam Griffis and Adam A. Whitley
Affiliations: Clemson University