_____
 ____  __
  ______     _______
    ____________________
           _______________
          _________________
          ________________
           ______________
            ____________
            __________
            ________
            _______
            _____
            _____
            ___
            ___
            ___
LATIN Papers

LATIN 2012
LATIN 2010
LATIN 2008
LATIN 2006
LATIN 2004
LATIN 2002
LATIN 2000
LATIN 1998
LATIN 1995
LATIN 1992



LATIN 2012


Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama and Antoine Vigneron, A Generalization of the Convex Kakeya Problem. [Bibtex]

Eric Angel, Evripidis Bampis and Vincent Chau, Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines. [Bibtex]

Esther M. Arkin, José Miguel Díaz-Báñez, Ferran Hurtado, Piyush Kumar, Joseph S. B. Mitchell, Belén Palop, Pablo Pérez-Lantero, Maria Saumell and Rodrigo I. Silveira, Bichromatic 2-Center of Pairs of Points. [Bibtex]

Vikraman Arvind, Partha Mukhopadhyay and Prajakta Nimbhorkar, Erdős-Rényi Sequences and Deterministic Construction of Expanding Cayley Graphs. [Bibtex]

Rafael da Ponte Barbosa and Yoshiko Wakabayashi, A Better Approximation Ratio and an IP Formulation for a Sensor Cover Problem. [Bibtex]

Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic and Peter Rossmanith, On the Advice Complexity of the Knapsack Problem. [Bibtex]

Nicolas Boria, Jérôme Monnot and Vangelis Th. Paschos, Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems. [Bibtex]

Prosenjit Bose, Rolf Fagerberg, André van Renssen and Sander Verdonschot, On Plane Constrained Bounded-Degree Spanners. [Bibtex]

Joshua Brody, Hongyu Liang and Xiaoming Sun, Space-Efficient Approximation Scheme for Circular Earth Mover Distance. [Bibtex]

Ana Busic, Nazim Fatès, Jean Mairesse and Irene Marcovici, Density Classification on Infinite Lattices and Trees. [Bibtex]

Jean Cardinal and Matias Korman, Coloring Planar Homothets and Three-Dimensional Hypergraphs. [Bibtex]

Armando Castañeda, Maurice Herlihy and Sergio Rajsbaum, An Equivariance Theorem with Applications to Renaming. [Bibtex]

Armando Castañeda, Damien Imbs, Sergio Rajsbaum and Michel Raynal, Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks. [Bibtex]

Eda Cesaratto and Brigitte Vallée, Pseudorandomness of a Random Kronecker Sequence. [Bibtex]

Richard Cole and Vijaya Ramachandran, Revisiting the Cache Miss Analysis of Multithreaded Algorithms. [Bibtex]

Robert Crowston, Gregory Gutin, Mark Jones, Venkatesh Raman and Saket Saurabh, Parameterized Complexity of MaxSat above Average. [Bibtex]

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Onufry Wojtaszczyk, Solving the 2-Disjoint Connected Subgraphs Problem Faster Than $2^n$. [Bibtex]

Daniel Dadush, A $O(1/\epsilon^2)^n$-Time Sieving Algorithm for Approximate Integer Programming. [Bibtex]

Pooya Davoodi, Michiel H. M. Smid and Freek van Walderveen, Two-Dimensional Range Diameter Queries. [Bibtex]

Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl and Andrzej Rucinski, An Improved Upper Bound on the Density of Universal Random Graphs. [Bibtex]

Volker Diekert, Jonathan Kausch and Markus Lohrey, Logspace Computations in Graph Groups and Coxeter Groups. [Bibtex]

Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Oscar Morales Ponce and Ladislav Stacho, Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points. [Bibtex]

Mitre Costa Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp Matthias Schäfer, Jayme Luiz Szwarcfiter and Alexandre Toma, On the Radon Number for $P_3$-Convexity. [Bibtex]

Tinaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof and Daniel Meister, Computing Minimum Geodetic Sets of Proper Interval Graphs. [Bibtex]

Zoltán Ésik and Szabolcs Iván, Hausdorff Rank of Scattered Context-Free Linear Orders. [Bibtex]

Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro and Shmuel Zaks, . [Bibtex]

MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Vahab S. Mirrokni and Sina Sadeghian Sadeghabad, On the Non-progressive Spread of Influence through Social Networks. [Bibtex]

Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela and Niko Välimäki, Forbidden Patterns. [Bibtex]

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner and Maximilian Witek, Structural Complexity of Multiobjective NP Search Problems. [Bibtex]

Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle and Yngve Villanger, $k$-Gap Interval Graphs. [Bibtex]

Pierre Fraigniaud and Andrzej Pelc, Decidability Classes for Mobile Agents Computing. [Bibtex]

Bin Fu, NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets. [Bibtex]

Martin Fürer, Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width. [Bibtex]

Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela and Jorma Tarhio, Indexed Multi-pattern Matching. [Bibtex]

Archontia C. Giannopoulou, Sudeshna Kolay and Saket Saurabh, New Lower Bound on Max Cut of Hypergraphs with an Application to $r$-Set Splitting. [Bibtex]

Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman and Ravi Sundaram, Cache Me If You Can: Capacitated Selfish Replication Games. [Bibtex]

Gero Greiner and Riko Jacob, The Efficiency of MapReduce in Parallel External Memory. [Bibtex]

Michel Habib, Antoine Mamcarz and Fabien de Montgolfier, Algorithms for Some $H$-Join Decompositions. [Bibtex]

Daniel Heldt, Kolja B. Knauer and Torsten Ueckerdt, On the Bend-Number of Planar and Outerplanar Graphs. [Bibtex]

Ahmed Helmi, Conrado Martínez and Alois Panholzer, Hiring above the $m$-th Best Candidate: A Generalization of Records in Permutations. [Bibtex]

Wiebke Höhn and Tobias Jacobs, On the Performance of Smith's Rule in Single-Machine Scheduling with Nonlinear Cost. [Bibtex]

Rohit Khandekar, Guy Kortsarz and Vahab S. Mirrokni, Advantage of Overlapping Clusters for Minimizing Conductance. [Bibtex]

Toryn Qwyllyn Klassen and Philipp Woelfel, Independence of Tabulation-Based Hash Classes. [Bibtex]

Martin Kutrib, Andreas Malcher and Giovanni Pighizzini, Oblivious Two-Way Finite Automata: Decidability and Complexity. [Bibtex]

Hélio B. Macêdo Filho, Raphael C. S. Machado and Celina M. Herrera de Figueiredo, Clique-Colouring and Biclique-Colouring Unichord-Free Graphs. [Bibtex]

Bernard Mans and Igor Shparlinski, Random Walks and Bisections in Random Circulant Graphs. [Bibtex]

Monaldo Mastrolilli, The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem. [Bibtex]

Basile Morcrette, Fully Analyzing an Algebraic Pólya Urn Model. [Bibtex]

Zeev Nutov, Degree-Constrained Node-Connectivity. [Bibtex]

Zeev Nutov, Survivable Network Activation Problems. [Bibtex]

Jiawei Qian, Frans Schalekamp, David P. Williamson and Anke van Zuylen, On the Integrality Gap of the Subtour LP for the 1,2-TSP. [Bibtex]

Hadas Shachnai, Gal Tamir and Tami Tamir, A Theory and Algorithms for Combinatorial Reoptimization. [Bibtex]

Amir Shpilka, Capacity Achieving Two-Write WOM Codes. [Bibtex]

Xiaoming Sun, Chengu Wang and Wei Yu, The Relationship between Inner Product and Counting Cycles. [Bibtex]

Linqing Tang and Peng Zhang, Approximating Minimum Label $s$-$t$ Cut via Linear Programming. [Bibtex]



[Top] [Home] [LATIN 2012]



LATIN 2010


Cristopher Moore, Continuous and Discrete Methods in Computer Science. [Bibtex]

Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky and Perouz Taslakian, Colorful Strips. [Bibtex]

Jonathan Backer and J. Mark Keil, The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions. [Bibtex]

Qianping Gu and Navid Imani, Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set. [Bibtex]

Eric Angel, Evripidis Bampis and Nicolas Thibault, Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machines. [Bibtex]

Martin Fürer, Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width. [Bibtex]

Nadja Betzler, Jiong Guo, Christian Komusiewicz and Rolf Niedermeier, Average Parameterization and Partial Kernelization for Computing Medians. [Bibtex]

Fedor V. Fomin, Daniel Lokshtanov, Fabrizio Grandoni and Saket Saurabh, Sharp Separation and Applications to Exact and Parameterized Algorithms. [Bibtex]

Tsunehiko Kameda, Ichiro Suzuki and John Z. Zhang, Finding the Minimum-Distance Schedule for a Boundary Searcher with a Flashlight. [Bibtex]

Salvatore La Torre, Parthasarathy Madhusudan and Gennaro Parlato, The Language Theory of Bounded Context-Switching. [Bibtex]

Diego Recalde, Cyriel Rutten, Petra Schuurman and Tjark Vredeveld, Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling. [Bibtex]

Britta Peis, Martin Skutella and Andreas Wiese, Packet Routing on the Grid. [Bibtex]

Michael D. Coury, Pavol Hell, Jan Kratochvíl and Tomás Vyskocil, Faithful Representations of Graphs by Islands in the Extended Grid. [Bibtex]

Gero Greiner and Riko Jacob, The I/O Complexity of Sparse Matrix Dense Matrix Multiplication. [Bibtex]

Piotr Indyk, Sparse Recovery Using Sparse Random Matrices. [Bibtex]

Johannes Fischer, Optimal Succinctness for Range Minimum Queries. [Bibtex]

Jérémy Barbay, Francisco Claude and Gonzalo Navarro, Compact Rich-Functional Binary Relation Representations. [Bibtex]

Sylvain Lombardy and Jacques Sakarovitch, Radix Cross-Sections for Length Morphisms. [Bibtex]

Viliam Geffert and Giovanni Pighizzini, Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata. [Bibtex]

Janusz A. Brzozowski, Galina Jirásková and Baiyu Li, Quotient Complexity of Ideal Languages. [Bibtex]

Frédérique Bassino, Laura Giambruno and Cyril Nicaud, Complexity of Operations on Cofinite Languages. [Bibtex]

Hagai Cohen and Ely Porat, Fast Set Intersection and Two-Patterns Matching. [Bibtex]

Joachim von zur Gathen, Alfredo Viola and Konstantin Ziegler, Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields. [Bibtex]

Beate Bollig, A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication. [Bibtex]

Manfred G. Madritsch and Brigitte Vallée, Modelling the LLL Algorithm by Sandpiles. [Bibtex]

Prosenjit Bose, Paz Carmi, Michiel H. M. Smid and Daming Xu, Communication-Efficient Construction of the Plane Localized Delaunay Graph. [Bibtex]

Dominik Gall, Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid and Hanjo Täubig, Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization. [Bibtex]

Petra Berenbrink, Robert Elsässer and Thomas Sauerwald, Randomised Broadcasting: Memory vs. Randomness. [Bibtex]

Vonjy Rasendrahasina and Vlady Ravelomanana, Limit Theorems for Random MAX-2-XORSAT. [Bibtex]

Per Austrin, Siavosh Benabbas and Avner Magen, On Quadratic Threshold CSPs. [Bibtex]

Carles Padró and Leonor Vázquez, Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming. [Bibtex]

Elizabeth Maltais and Lucia Moura, Finding the Best CAFE Is NP-Hard. [Bibtex]

Anna Gál and Jing-Tang Jang, The Size and Depth of Layered Boolean Circuits. [Bibtex]

Pankaj K. Agarwal, Jeff M. Phillips and Bardia Sadri, Lipschitz Unimodal and Isotonic Regression on Paths and Trees. [Bibtex]

Daniel Panario, Brett Stevens and Qiang Wang, Ambiguity and Deficiency in Costas Arrays and APN Permutations. [Bibtex]

Sergio Rajsbaum, Iterated Shared Memory Models. [Bibtex]

Emden R. Gansner, Yifan Hu, Michael Kaufmann and Stephen G. Kobourov, Optimal Polygonal Representation of Planar Graphs. [Bibtex]

Adrian Dumitrescu and Minghui Jiang, Minimum-Perimeter Intersecting Polygons. [Bibtex]

Qi Cheng and Yu-Hsin Li, Finding the Smallest Gap between Sums of Square Roots. [Bibtex]

Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara and Perouz Taslakian, Matching Points with Things. [Bibtex]

Bettina Speckmann and Kevin Verbeek, Homotopic Rectilinear Routing with Few Links and Thick Edges. [Bibtex]

Alexis Ballier, Bruno Durand and Emmanuel Jeandel, Tilings Robust to Errors. [Bibtex]

Steven Bitner, Yam Ki Cheung, Atlas F. Cook, Ovidiu Daescu, Anastasia Kurdia and Carola Wenk, Visiting a Sequence of Points with a Bevel-Tip Needle. [Bibtex]

MohammadHossein Bateni and MohammadTaghi Hajiaghayi, Euclidean Prize-Collecting Steiner Forest. [Bibtex]

MohammadTaghi Hajiaghayi and Arefeh A. Nasri, Prize-Collecting Steiner Networks via Iterative Rounding. [Bibtex]

René van Bevern, Hannes Moser and Rolf Niedermeier, Kernelization through Tidying. [Bibtex]

Mark van Hoeij and Andrew Novocin, Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials. [Bibtex]

Christine Chung, Katrina Ligett, Kirk Pruhs and Aaron Roth, The Power of Fair Pricing Mechanisms. [Bibtex]

Vahab S. Mirrokni, S. Muthukrishnan and Uri Nadav, Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization. [Bibtex]

Leslie G. Valiant, Some Observations on Holographic Algorithms. [Bibtex]

Jaroslaw Byrka, Andreas Karrenbauer and Laura Sanità, The Interval Constrained 3-Coloring Problem. [Bibtex]

Paul S. Bonsma and Felix Breuer, Counting Hexagonal Patches and Independent Sets in Circle Graphs. [Bibtex]

Yuichi Asahiro, Eiji Miyano and Kazuaki Samizo, Approximating Maximum Diameter-Bounded Subgraphs. [Bibtex]

Kunal Dutta and C. R. Subramanian, Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration. [Bibtex]

Qi Ge and Daniel Stefankovic, The Complexity of Counting Eulerian Tours in 4-Regular Graphs. [Bibtex]

Andreas Brandstädt, Christian Hundt and Ragnar Nevries, Efficient Edge Domination on Hole-Free Graphs in Polynomial Time. [Bibtex]

Marek Karpinski, Andrzej Rucinski and Edyta Szymanska, Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. [Bibtex]

Amalia Duch, Rosa M. Jiménez and Conrado Martínez, Rank Selection in Multidimensional Data. [Bibtex]

Prosenjit Bose, Karim Douïeb, Vida Dujmovic and John Howat, Layered Working-Set Trees. [Bibtex]

Paolo Ferragina, Travis Gagie and Giovanni Manzini, Lightweight Data Indexing and Compression in External Memory. [Bibtex]



[Top] [Home] [LATIN 2010]



LATIN 2008


GaHyun Park, Hsien-Kuei Hwang, Pierre Nicodème and Wojciech Szpankowski, Profile of Tries. [Bibtex]

Hervé Daudé and Vlady Ravelomanana, Random 2-{XORSAT} at the Satisfiability Threshold. [Bibtex]

Ivan Rapaport, Karol Suchan, Ioan Todinca and Jacques Verstraëte, On Dissemination Thresholds in Regular and Irregular Graph Classes. [Bibtex]

Anupam Gupta and Kunal Talwar, How to Complete a Doubling Metric. [Bibtex]

Stanislav Angelov, Keshav Kunal and Andrew McGregor, Sorting and Selection with Random Costs. [Bibtex]

Dominik Scheder, Guided Search and a Faster Deterministic Algorithm for 3-{SAT}. [Bibtex]

Mukul S. Bansal, Jianrong Dong and David Fernández-Baca, Comparing and Aggregating Partially Resolved Trees. [Bibtex]

Raphael M. Jungers, Vladimir Protasov and Vincent D. Blondel, Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices. [Bibtex]

Oscar H. Ibarra, Juhani Karhumäki and Alexander Okhotin, On Stateless Multihead Automata: Hierarchies and the Emptiness Problem. [Bibtex]

Andreas Maletti, Myhill-Nerode Theorem for Recognizable Tree Series Revisited. [Bibtex]

Sergey Afonin, The View Selection Problem for Regular Path Queries. [Bibtex]

Rodrigo I. Silveira and Marc J. van Kreveld, Optimal Higher Order Delaunay Triangulations of Polygons. [Bibtex]

Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman and Shakhar Smorodinsky, Coloring Geometric Range Spaces. [Bibtex]

Jurek Czyzowicz, Stefan Dobrev, Thomas Fevens, H. González-Aguilar, Evangelos Kranakis, Jaroslav Opatrny and Jorge Urrutia, Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes. [Bibtex]

Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin and Michiel H. M. Smid, Spanners of Complete $k$-Partite Geometric Graphs. [Bibtex]

Arvind Gupta, Pavol Hell, Mehdi Karimi and Arash Rafiey, Minimum Cost Homomorphisms to Reflexive Digraphs. [Bibtex]

Fedor V. Fomin, Jan Kratochvíl, Daniel Lokshtanov, Federico Mancini and Jan Arne Telle, On the Complexity of Reconstructing $H$-free Graphs from Their Star Systems. [Bibtex]

Bruce Reed and Zhentao Li, Optimization and Recognition for $K_5$-minor Free Graphs in Linear Time. [Bibtex]

Pinar Heggernes, Dieter Kratsch and Daniel Meister, Bandwidth of Bipartite Permutation Graphs in Polynomial Time. [Bibtex]

Christine Chung, Kirk Pruhs and Patchrawat Uthaisombut, The Online Transportation Problem: On the Exponential Boost of One Extra Server. [Bibtex]

Nikhil Bansal, David P. Bunde, Ho-Leung Chan and Kirk Pruhs, Average Rate Speed Scaling. [Bibtex]

Marcin Bienkowski and Aleksander Madry, Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers. [Bibtex]

Leah Epstein and Rob van Stee, Maximizing the Minimum Load for Selfish Agents. [Bibtex]

Joachim von zur Gathen and Igor Shparlinski, Approximate Polynomial gcd: Small Degree and Small Height Perturbations. [Bibtex]

Igor Shparlinski, Pseudorandom Graphs from Elliptic Curves. [Bibtex]

Ali Akhavi and Damien Stehlé, Speeding-Up Lattice Reduction with Random Projections (Extended Abstract). [Bibtex]

Elad Hazan, Sparse Approximate Solutions to Semidefinite Programs. [Bibtex]

Gérard Cornuéjols and Fran&;ois Margot, On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints. [Bibtex]

Cristina G. Fernandes, Carlos Ferreira, Christian Tjandraatmadja and Yoshiko Wakabayashi, A Polyhedral Investigation of the {LCS} Problem and a Repetition-Free Variant. [Bibtex]

Martin Hoefer, Competitive Cost Sharing with Economies of Scale. [Bibtex]

George Karakostas and Euripides Markou, Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes. [Bibtex]

Luís M. S. Russo, Gonzalo Navarro and Arlindo L. Oliveira, Fully-Compressed Suffix Trees. [Bibtex]

Rodrigo González and Gonzalo Navarro, Improved Dynamic Rank-Select Entropy-Bound Structures. [Bibtex]

Rina Panigrahy, An Improved Algorithm Finding Nearest Neighbor Using Kd-trees. [Bibtex]

Spyros Angelopoulos, Reza Dorrigiv and Alejandro López-Ortiz, List Update with Locality of Reference. [Bibtex]

Zeev Nutov, Approximating Steiner Networks with Node Weights. [Bibtex]

Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov and Elena Tsanko, Approximating Minimum-Power Degree and Connectivity Problems. [Bibtex]

Amol Deshpande, Samir Khuller, Azarakhsh Malekian and Mohammed Toossi, Energy Efficient Monitoring in Sensor Networks. [Bibtex]

Brian C. Dean, Adam Griffis and Adam Whitley, Approximation Algorithms for $k$-Hurdle Problems. [Bibtex]

Seok-Hee Hong and Hiroshi Nagamochi, Approximating Crossing Minimization in Radial Layouts. [Bibtex]

Andrzej Dudek and Vojtech Rödl, New Upper Bound on Vertex Folkman Numbers. [Bibtex]

Andreas Brandstädt and Christian Hundt, Ptolemaic Graphs and Interval Graphs Are Leaf Powers. [Bibtex]

Binh-Minh Bui-Xuan and Michel Habib, A Representation Theorem for Union-Difference Families and Application. [Bibtex]

Conrado Martínez, Lucia Moura, Daniel Panario and Brett Stevens, Algorithms to Locate Errors Using Covering Arrays. [Bibtex]

Pavol Hell, André Raspaud and Juraj Stacho, On Injective Colourings of Chordal Graphs. [Bibtex]

Paul S. Bonsma and Florian Zickfeld, Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. [Bibtex]

Juraj Stacho, On 2-Subcolourings of Chordal Graphs. [Bibtex]

Feodor F. Dragan, Chenyu Yan and Yang Xiang, Collective Additive Tree Spanners of Homogeneously Orderable Graphs. [Bibtex]

Christine Cheng, The Generalized Median Stable Matchings: Finding Them Is Not That Easy. [Bibtex]

Baruch Awerbuch and Rohit Khandekar, Stateless Near Optimal Flow Control with Poly-logarithmic Convergence. [Bibtex]

Richard McCutchen, The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences. [Bibtex]

Evangelos Kranakis, Danny Krizanc and Pat Morin, Randomized Rendez-Vous with Limited Memory. [Bibtex]

Marshall W. Bern and Barry Hayes, Origami Embedding of Piecewise-Linear Two-Manifolds. [Bibtex]

Sergey Bereg, Minghui Jiang, Wencheng Wang, Boting Yang and Binhai Zhu, Simplifying {3D} Polygonal Chains Under the Discrete Fréchet Distance. [Bibtex]

Mario Lopez and Yan Mayster, Weighted Rectilinear Approximation of Points in the Plane. [Bibtex]

Imre Bárány, Attila Pór and Pavel Valtr, Paths with no Small Angles. [Bibtex]

Domingos Dellamonica Jr., Simpler Constant-Seed Condensers. [Bibtex]

Kooshiar Azimian and Mario Szegedy, Parallel Repetition of the Odd Cycle Game. [Bibtex]

Yakov Nekrich, {I/O}-Efficient Point Location in a Set of Rectangles. [Bibtex]

Regant Y. S. Hung and Hing-Fung Ting, Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream. [Bibtex]

Falk Hüffner, Christian Komusiewicz, Hannes Moser and Rolf Niedermeier, Fixed-Parameter Algorithms for Cluster Vertex Deletion. [Bibtex]

A. Abouelaoualim, Kinkar Chandra Das, L. Faria, Yannis Manoussakis, Carlos Martinhon and Rachid Saad, Paths and Trails in Edge-Colored Graphs. [Bibtex]

Andrzej Lingas and Eva-Marta Lundell, Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs. [Bibtex]

Thomas Erlebach and Erik Jan van Leeuwen, Domination in Geometric Intersection Graphs. [Bibtex]

Gábor Ivanyos, Luc Sanselme and Miklos Santha, An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups. [Bibtex]

Yoshifumi Inui and Fran&;ois Le Gall, Quantum Property Testing of Group Solvability. [Bibtex]

Martin Fürer, Solving {NP}-Complete Problems with Quantum Search. [Bibtex]



[Top] [Home] [LATIN 2008]



LATIN 2006


Ricardo Baeza-Yates, Algorithmic Challenges in Web Search Engines. [Bibtex]

Anne Condon, RNA Molecules: Glimpses Through an Algorithmic Lens. [Bibtex]

Ferran Hurtado, Squares. [Bibtex]

R. Ravi, Matching Based Augmentations for Approximating Connectivity Problems. [Bibtex]

Madhu Sudan, Modelling Errors and Recovery for Communication. [Bibtex]

Sergio Verdú, Lossless Data Compression Via Error Correction. [Bibtex]

Avi Wigderson, The Power and Weakness of Randomness in Computation. [Bibtex]

Saurabh Agarwal and Gudmund Skovbjerg Frandsen, A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. [Bibtex]

Nir Ailon, Steve Chien and Cynthia Dwork, On Clusters in Markov Chains. [Bibtex]

Miklós Ajtai, Cynthia Dwork and Larry J. Stockmeyer, An Architecture for Provably Secure Computation. [Bibtex]

Elói Araújo and José Soares, Scoring Matrices That Induce Metrics on Sequences. [Bibtex]

Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman and Michiel H. M. Smid, Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. [Bibtex]

Boris Aronov, Alan R. Davis, John Iacono and Albert Siu Cheong Yu, The Complexity of Diffuse Reflections in a Simple Polygon. [Bibtex]

Argimiro Arratia and Carlos Ortiz, Counting Proportions of Sets: Expressive Power with Almost Order. [Bibtex]

Abdullah N. Arslan, Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets. [Bibtex]

Nuttapong Attrapadung, Yang Cui, David Galindo, Goichiro Hanaoka, Ichiro Hasuo, Hideki Imai, Kanta Matsuura, Peng Yang and Rui Zhang, Relations Among Notions of Security for Identity Based Encryption Schemes. [Bibtex]

Ilya Baran, Erik D. Demaine and Dmitriy A. Katz, Optimally Adaptive Integration of Univariate Lipschitz Functions. [Bibtex]

Benjamín René Callejas Bedregal and Santiago Figueira, Classical Computability and Fuzzy Turing Machines. [Bibtex]

Boaz Ben-Moshe, Binay K. Bhattacharya and Qiaosheng Shi, An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees. [Bibtex]

Thorsten Bernholt and Thomas Hofmeister, An Algorithm for a Generalized Maximum Subsequence Problem. [Bibtex]

Nayantara Bhatnagar, Dana Randall, Vijay V. Vazirani and Eric Vigoda, Random Bichromatic Matchings. [Bibtex]

Béla Bollobás, Guy Kindler, Imre Leader and Ryan O'Donnell, Eliminating Cycles in the Discrete Torus. [Bibtex]

Claudson F. Bornstein, Eduardo Sany Laber and Marcelo Mas, On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions. [Bibtex]

Jérémie Bourdon and Brigitte Vallée, Pattern Matching Statistics on Correlated Sources. [Bibtex]

Patricia Bouyer, Nicolas Markey and Pierre-Alain Reynier, Robust Model-Checking of Linear-Time Properties in Timed Automata. [Bibtex]

Hajo Broersma, Matthew Johnson, Daniël Paulusma and Iain A. Stewart, The Computational Complexity of the Parallel Knock-Out Problem. [Bibtex]

Gruia Calinescu, Adrian Dumitrescu and János Pach, Reconfigurations in Graphs and Grids. [Bibtex]

Laura Chaubard, C-Varieties, Actions and Wreath Product. [Bibtex]

Edgar Chávez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho and Jorge Urrutia, Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. [Bibtex]

Vicky Choi and Navin Goyal, An Efficient Approximation Algorithm for Point Pattern Matching Under Noise. [Bibtex]

Marek Chrobak, Claire Kenyon, John Noga and Neal E. Young, Oblivious Medians Via Online Bidding. [Bibtex]

Corinna Cortes, Mehryar Mohri, Ashish Rastogi and Michael Riley, Efficient Computation of the Relative Entropy of Probabilistic Automata. [Bibtex]

Ho-Kwok Dai and Hung-Chi Su, A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences. [Bibtex]

Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh and Mihai Patrascu, De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space). [Bibtex]

Sandeep Dey and Nicolas Schabanel, Customized Newspaper Broadcast: Data Broadcast with Dependencies. [Bibtex]

Gabriele Di Stefano, Stefan Krause, Marco E. Lübbecke and Uwe T. Zimmermann, On Minimum k-Modal Partitions of Permutations. [Bibtex]

Frederic Dorn and Jan Arne Telle, Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm. [Bibtex]

Douglas G. Down and George Karakostas, Maximizing Throughput in Queueing Networks with Limited Flexibility. [Bibtex]

Feodor F. Dragan and Chenyu Yan, Network Flow Spanners. [Bibtex]

Khaled Elbassioni, Finding All Minimal Infrequent Multi-dimensional Intervals. [Bibtex]

Roee Engelberg, Jochen Könemann, Stefano Leonardi and Joseph Naor, Cut Problems in Graphs with a Budget Constraint. [Bibtex]

Martin Farach-Colton, Rohan J. Fernandes and Miguel A. Mosteiro, Lower Bounds for Clear Transmissions in Radio Networks. [Bibtex]

Nazim Fatès, Damien Regnault, Nicolas Schabanel and Eric Thierry, Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. [Bibtex]

Hervé Fournier and Antoine Vigneron, Lower Bounds for Geometric Diameter Problems. [Bibtex]

Pierre Fraigniaud and Nicolas Nisse, Connected Treewidth and Connected Graph Searching. [Bibtex]

Martin Fürer, A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs. [Bibtex]

Eli Gafni, Sergio Rajsbaum, Michel Raynal and Corentin Travers, The Committee Decision Problem. [Bibtex]

Ling Gai and Guochuan Zhang, Common Deadline Lazy Bureaucrat Scheduling Revisited. [Bibtex]

Joachim Giesen, Eva Schuberth and Milos Stojakovic, Approximate Sorting. [Bibtex]

Michel X. Goemans and Jan Vondrák, Stochastic Covering and Adaptivity. [Bibtex]

Parikshit Gopalan, Venkatesan Guruswami and Richard J. Lipton, Algorithms for Modular Counting of Roots of Multivariate Polynomials. [Bibtex]

Venkatesan Guruswami and Valentine Kabanets, Hardness Amplification Via Space-Efficient Direct Products. [Bibtex]

Mikael Hammar, Bengt J. Nilsson and Mia Persson, The Online Freeze-Tag Problem. [Bibtex]

Herman J. Haverkort and Laura Toma, I/O-Efficient Algorithms on Near-Planar Graphs. [Bibtex]

Pinar Heggernes and Federico Mancini, Minimal Split Completions of Graphs. [Bibtex]

Regant Y. S. Hung and Hing-Fung Ting, Design and Analysis of Online Batching Systems. [Bibtex]

Wojciech Jawor, Marek Chrobak and Christoph Dürr, Competitive Analysis of Scheduling Algorithms for Aggregated Links. [Bibtex]

James King, A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains. [Bibtex]

Goran Konjevod, Andréa W. Richa and Donglin Xia, On Sampling in Higher-Dimensional Peer-to-Peer Systems. [Bibtex]

Evangelos Kranakis, Danny Krizanc and Euripides Markou, Mobile Agent Rendezvous in a Synchronous Torus. [Bibtex]

Lap Chi Lau and Michael Molloy, Randomly Colouring Graphs with Girth Five and Large Maximum Degree. [Bibtex]

Orlando Lee and Aaron Williams, Packing Dicycle Covers in Planar Graphs with No K5-e Minor. [Bibtex]

Loïck Lhote and Brigitte Vallée, Sharp Estimates for the Main Parameters of the Euclid Algorithm. [Bibtex]

Veli Mäkinen and Gonzalo Navarro, Position-Restricted Substring Searching. [Bibtex]

Yan Mayster and Mario A. Lopez, Rectilinear Approximation of a Set of Points in the Plane. [Bibtex]

Frédéric Mazoit, The Branch-Width of Circular-Arc Graphs. [Bibtex]

Eduardo Moreno and Martín Matamala, Minimal Eulerian Circuit in a Labeled Digraph. [Bibtex]

Frank Neumann and Marco Laumanns, Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization. [Bibtex]

Nadia Pisanti, Alexandra M. Carvalho, Laurent Marsan and Marie-France Sagot, RISOTTO: Fast Extraction of Motifs with Mismatches. [Bibtex]

Mariko Sakashita, Kazuhisa Makino and Satoru Fujishige, Minimum Cost Source Location Problems with Flow Requirements. [Bibtex]

Daniel Sawitzki, Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms. [Bibtex]

Igor Shparlinski and Arne Winterhof, Constructions of Approximately Mutually Unbiased Bases. [Bibtex]

Yngve Villanger, Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In. [Bibtex]



[Top] [Home] [LATIN 2006]



LATIN 2004


Mike Paterson, Analysis of Scheduling Algorithms for Proportionate Fairness. [Bibtex]

Yoshiharu Kohayakawa, Advances in the Regularity Method. [Bibtex]

Cynthia Dwork, Fighting Spam: The Science. [Bibtex]

Jean-Eric Pin, The consequences of Imre Simon's work in the theory of automata, languages and semigroups. [Bibtex]

Eduardo Sany Laber, Renato Carmo and Yoshiharu Kohayakawa, Querying Priced Information in Databases: the Conjuntive Case. [Bibtex]

Funda Ergun, S. Muthukrishnan and Cenk Sahinalp, Sublinear Methods for Detecting Periodic Trends in Data Streams. [Bibtex]

Graham Cormode and S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and its Applications. [Bibtex]

Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro, Rotation and Lighting Invariant Template Matching. [Bibtex]

Josep Díaz, Maria Serna and Nicholas Wormald, Computation of the bisection width for random d-regular graphs. [Bibtex]

Christian Borgs, Jennifer Chayes, Stephan Mertens and Boris Pittel, Constrained Integer Partitions. [Bibtex]

Abraham Flaxman, David Gamarnik and Gregory Sorkin, Embracing the Giant Component. [Bibtex]

Dimitris Achlioptas, Mike Molloy, Cristopher Moore and Frank Van Bussel, Sampling Grid Colourings with Fewer Colours. [Bibtex]

Lane Hemaspaandra, Mitsunori Ogihara, Mohammed Zaki and Marius Zimand, The Complexity of Finding Top-Toda-Equivalence-Class~Members. [Bibtex]

Tomás Feder, Pavol Hell, Sulamita Klein, Loana Tito Nogueira and Fábio Protti, List Partitions of Chordal Graphs. [Bibtex]

Erik D. Demaine, Fedor Fomin, Mohammad Taghi Hajiaghayi and Dimitrios M. Thilikos, Bidimensional Parameters and Local Treewidth. [Bibtex]

Frank Gurski and Egon Wanke, Vertex Disjoint Paths on Clique-Width Bounded Graphs. [Bibtex]

Frederic Gardi, On partitioning interval and circular-arc graphs into proper interval subgraphs with applications. [Bibtex]

Pierre Fraigniaud, Leszek Gasieniec, Dariusz R. Kowalski and Andrzej Pelc, Collective tree exploration. [Bibtex]

Alper Üngör, Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations. [Bibtex]

Hervé Brönnimann and Timothy Chan, Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. [Bibtex]

Claudio Gutierrez, Flavio Gutierrez and Maria-Cecilia Rivara, A Geometric Approach to the Bisection Method. [Bibtex]

Ho-Kwok Dai and X. W. Zhang, Improved Linear Expected-Time Algorithms for Computing Maxima. [Bibtex]

Jens S. Kohrt and Kirk Pruhs, Constant Approximation Algorithm for Sorting Buffers. [Bibtex]

Kirk Pruhs and Gerhard Woeginger, Approximation schemes for a class of subset selection problems. [Bibtex]

Prabhakar Gubbala and Balaji Raghavachari, Finding k-connected subgraphs with minimum average weight. [Bibtex]

Ke Yang, On the (Im)possibility of Non-interactive Correlation Distillation. [Bibtex]

Volker Diekert and Paul Gastin, Pure future local temporal logics are expressively complete for Mazurkiewicz traces. [Bibtex]

Sylvain Lombardy and Jacques Sakarovitch, How expressions code for automata. [Bibtex]

Shigeki Akiyama, Frédérique Bassino and Christiane Frougny, Automata for arithmetic Meyer sets. [Bibtex]

Manuel Bodirsky, Tobias Gärtner, Timo von Oertzen and Jan Schwinghammer, Efficiently Computing the Density of Regular Languages. [Bibtex]

Maxime Crochemore, Costas Iliopoulos, Manal Mohamed and Marie-France Sagot, Longest Repeats with a Block of Don't Cares. [Bibtex]

John Rhodes and Benjamin Steinberg, Join Irreducible Pseudovarieties, Group Mapping and Kovacs-Newman Semigroups. [Bibtex]

Olivier Carton and Chloe Rispal, Complementation of rational sets on scattered linear orderings of finite rank. [Bibtex]

Marcos Kiwi, Martin Loebl and Jirí Matousek, Expected length of the longest common subsequence for large alphabets. [Bibtex]

Gadiel Seroussi, Universal types and simulation of individual sequences. [Bibtex]

Gérard Cohen and Hans Georg Schaathun, Separating Codes: Constructions and Upper Bounds. [Bibtex]

Sergei Bespamyatnikh, Encoding Homotopy of Paths in the Plane. [Bibtex]

Saverio Caminiti, Irene Finocchi and Rossella Petreschi, A unified approach to coding labeled trees. [Bibtex]

Hervé Brönnimann and Marc Glisse, Cost Optimal Trees for Ray Shooting. [Bibtex]

Flavio Keidi Miyazawa and Yoshiko Wakabayashi, Packing problems with orthogonal rotations. [Bibtex]

Alantha Newman and Matthias Ruhl, Combinatorial Problems on Strings with Applications to Protein Folding. [Bibtex]

Mark Cieliebak and Stephan Eidenbenz, Measurement Errors Make the Partial Digest Problem NP-hard. [Bibtex]

Jean Cardinal and Stefan Langerman, Designing Small Keyboards is Hard. [Bibtex]

James R. Lee, Manor Mendel and Assaf Naor, Metric structures in $L_1$: Dimension, snowflakes, and average distortion. [Bibtex]

Richard J. Lipton and Evangelos Markakis, Nash Equilibria via Polynomial Equations. [Bibtex]

Raja Jothi and Balaji Raghavachari, Minimum Latency Tours and the k-Traveling Repairmen Problem. [Bibtex]

Nikhil Bansal and Kirk Pruhs, Server Scheduling in the Weighted $l_p$ Norm. [Bibtex]

Martin Fürer, An Improved Communication-Randomness Tradeoff. [Bibtex]

Paul Gastin, Benjamin Lerman and Marc Zeitoun, Distributed games and distributed control for asynchronous systems. [Bibtex]

Mihai Badoiu and Erik D. Demaine, A Simplified and Dynamic Unified Structure. [Bibtex]

Ali Akhavi and Celine Moreira Dos Santos, Another view of the Gaussian algorithm. [Bibtex]

Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan, Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections. [Bibtex]

Jesper Jansson, Joseph H.-K. Ng, Kunihiko Sadakane and Wing-Kin Sung, Rooted Maximum Agreement Supertrees. [Bibtex]

Edith Hemaspaandra, Holger Spakowski and Mayur Thakur, Complexity of Cycle Length Modularity Problems in Graphs. [Bibtex]

Dusan Guller, Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices. [Bibtex]

Olga Tveretina and Hans Zantema, A Proof System and a Decision Procedure for Equality Logic. [Bibtex]

Argimiro Arratia and Carlos Ortiz, Approximating the expressive power of logics in finite models. [Bibtex]

Joachim von zur Gathen, Arithmetic circuits for discrete logarithms. [Bibtex]

Jeff Edmonds, On the Competitiveness of AIMD-TCP within a General Network. [Bibtex]

Mark Cieliebak, Gathering Non-Oblivious Mobile Robots. [Bibtex]

Bernard Mans and Igor Shparlinski, Bisecting and Gossiping in Circulant Graphs. [Bibtex]

Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro and Cindy Sawchuk, Mobile Agent Rendezvous in a Ring. [Bibtex]

Jeremy Elson, Richard Karp, Christos Papadimitriou and Scott Shenker, Global Synchronization in Sensornets. [Bibtex]



[Top] [Home] [LATIN 2004]



LATIN 2002


Jennifer Chayes, Phase Transitions in Computer Science. [Bibtex]

Christos Papadimitriou, The Internet, the Web, and Algorithms. [Bibtex]

Joel Spencer, Erdos Magic. [Bibtex]

Jorge Urrutia, Open Problems in Computational Geometry. [Bibtex]

Umesh V. Vazirani, Quantum Algorithms. [Bibtex]

Mihalis Yannakakis, Testing and Checking of Finite State Systems. [Bibtex]

Fabrizio Luccio and Linda Pagli, From Algorithms to Cryptography. [Bibtex]

Eric Goubault and Martin Raussen, Dihomotopy as a Tool in State Space Analysis. [Bibtex]

Abdullah N. Arslan and Ömer Egecioglu, Algorithms for Local Alignment with Length Constraints. [Bibtex]

Marília D. V. Braga and Joao Meidanis, An Algorithm That Builds a Set of Strings Given Its Overlap Graph. [Bibtex]

Christiane Frougny, Conversion between Two Multiplicatively Dependent Linear Numeration Systems. [Bibtex]

Sylvain Lombardy and Jacques Sakarovitch, Star Height of Reversible Languages and Universal Automata. [Bibtex]

Howard Straubing and Denis Thérien, Weakly Iterated Block Products of Finite Monoids. [Bibtex]

Maria Isabel Gonzalez Vasco, Mats Näslund and Igor Shparlinski, The Hidden Number Problem in Extension Fields and Its Applications. [Bibtex]

Theodoulos Garefalakis, The Generalized Weil Pairing and the Discrete Logarithm Problem on Elliptic Curves. [Bibtex]

Rod Canfield, Sylvie Corteel and Pawel Hitczenko, Random Partitions with Non Negative rth Differences. [Bibtex]

Frédérique Bassino, Beta-Expansions for Cubic Pisot Numbers. [Bibtex]

Prosenjit Bose and Qingda Wang, Facility Location Constrained to a Polygonal Domain. [Bibtex]

Hanno Lefmann and Niels Schmitt, A Deterministic Polynomial Time Algorithm for Heilbronn's Problem in Dimension Three. [Bibtex]

Edgar Chávez and Gonzalo Navarro, A Metric Index for Approximate String Matching. [Bibtex]

Wojciech Rytter, On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm. [Bibtex]

Derek G. Corneil, Feodor F. Dragan and Ekkehard Köhler, On the Power of BFS to Determine a Graphs Diameter. [Bibtex]

Martín Matamala, Erich Prisner and Ivan Rapaport, k-pseudosnakes in Large Grids. [Bibtex]

Tiziana Calamoneri and Rossella Petreschi, L(2, 1)-Coloring Matrogenic Graphs. [Bibtex]

Ruy Luiz Milidiú, Artur Alves Pessoa and Eduardo Sany Laber, Pipeline Transportation of Petroleum Products with No Due Dates. [Bibtex]

Enrico Pontelli and Desh Ranjan, Ancestor Problems on Pure Pointer Machines. [Bibtex]

Renato Carmo, Jair Donadelli, Yoshiharu Kohayakawa and Eduardo Sany Laber, Searching in Random Partially Ordered Sets. [Bibtex]

Brett Stevens and Eric Mendelsohn, Packing Arrays. [Bibtex]

Michael Drmota and Wojciech Szpankowski, Generalized Shannon Code Minimizes the Maximal Redundancy. [Bibtex]

S. Muthukrishnan and Cenk Sahinalp, An Improved Algorithm for Sequence Comparison with Block Reversals. [Bibtex]

Blaise Genest and Anca Muscholl, Pattern Matching and Membership for Hierarchical Message Sequence Charts. [Bibtex]

Jianer Chen and Iyad Kanj, Improved Exact Algorithms for MAX-SAT. [Bibtex]

Steffen van Bakel and Mariangiola Dezani-Ciancaglini, Characterising Strong Normalisation for Explicit Substitutions. [Bibtex]

Roel Bloo, Fairouz Kamareddine, Twan Laan and Rob Nederpelt, Parameters in Pure Type Systems. [Bibtex]

Rusins Freivalds and Carl H. Smith, Category, Measure, Inductive Inference: A Triality Theorem and Its Applications. [Bibtex]

Frédéric Herbreteau, Franck Cassez, Alain Finkel, Olivier Roux and Grégoire Sutre, Verification of Embedded Reactive Fiffo Systems. [Bibtex]

Alejandro Hevia and Marcos Kiwi, Electronic Jury Voting Protocols. [Bibtex]

Gonzalo Tornaría, Square Roots Modulo p. [Bibtex]

Goran Konjevod, Soohyun Oh and Andréa W. Richa, Finding Most Sustainable Paths in Networks with Time-Dependent Edge Reliabilities. [Bibtex]

Jean-Christophe Dubacq and Véronique Terrier, Signals for Cellular Automata in Dimension 2 or Higher. [Bibtex]

Paolo Boldi and Sebastiano Vigna, Holographic Trees. [Bibtex]

Prosenjit Bose, Luc Devroye, William S. Evans and David G. Kirkpatrick, On the Spanning Ratio of Gabriel Graphs and beta-skeletons. [Bibtex]

Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison and Godfried T. Toussaint, In-Place Planar Convex Hull Algorithms. [Bibtex]

Michael A. Bender and Martin Farach-Colton, The Level Ancestor Problem Simplified. [Bibtex]

Claudson F. Bornstein and Santosh Vempala, Flow Metrics. [Bibtex]

Howard Straubing, On Logical Descriptions of Regular Languages. [Bibtex]

Mario Szegedy and Xiaomin Chen, Computing Boolean Functions from Multiple Faulty Copies of Input Bits. [Bibtex]

Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita, Inapproximability Results on Stable Marriage Problems. [Bibtex]

Hadas Shachnai and Tami Tamir, Tight Bounds for Online Class-Constrained Packing. [Bibtex]

R. Sai Anand and Thomas Erlebach, On-line Algorithms for Edge-Disjoint Paths in Trees of Rings. [Bibtex]

James Abello, Mauricio G. C. Resende and Sandra Sudarsky, Massive Quasi-Clique Detection. [Bibtex]

Jochen Alber and Rolf Niedermeier, Improved Tree Decomposition Based Algorithms for Domination-like Problems. [Bibtex]



[Top] [Home] [LATIN 2002]



LATIN 2000


Yoshiharu Kohayakawa and Vojtech Rödl, Algorithmic Aspects of Regularity. [Bibtex]

Michele Zito, Small Maximal Matchings in Random Graphs. [Bibtex]

Vlady Ravelomanana and Loÿs Thimonier, Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs. [Bibtex]

Andreas Goerdt and Michael Molloy, Analysis of Edge Deletion Processes on Faulty Random Regular Graphs. [Bibtex]

Yoshiharu Kohayakawa, Vojtech Rödl and J. Skodan, Equivalent Conditions for Regularity (Extended Abstract). [Bibtex]

Flavio Keidi Miyazawa and Yoshiko Wakabayashi, Cube Packing. [Bibtex]

Klaus Jansen, Monaldo Mastrolilli and Roberto Solis-Oba, Approximation Algorithms for Flexible Job Shop Problems. [Bibtex]

Stephen Taylor, Emerging Behavior as Binary Search Trees Are Symmetrically Updated. [Bibtex]

Michael A. Bender and Martin Farach-Colton, The LCA Problem Revisited. [Bibtex]

Myra B. Cohen and Charles J. Colbourn, Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays. [Bibtex]

Lucia Moura, Rank Inequalities for Packing Designs and Sparse Triple Systems. [Bibtex]

Brett Stevens, The Anti-Oberwolfach Solution: Pancyclic 2- Factorizations of Complete Graphs. [Bibtex]

Prabhakar Raghavan, Graph Structure of the Web: A Survey. [Bibtex]

Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce Reed and Udi Rotics, Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract). [Bibtex]

Cláudia Linhares Sales and Frédéric Maffray, On Dart-Free Perfectly Contractile Graphs. Extended Abstract. [Bibtex]

Celina M. Herrera de Figueiredo, Célia Picinin de Mello and Carmen Ortiz, Edge Colouring Reduced Indifference Graphs. [Bibtex]

David Avis, Caterina De Simone and Paolo Nobili, Two Conjectures on the Chromatic Polynomial. [Bibtex]

Celina M. H. de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa and Bruce Reed, Finding Skew Partitions Efficiently. [Bibtex]

Allan Borodin, Ran El-Yaniv and Vincent Gogan, On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract). [Bibtex]

Valentine Kabanets, Almost k-Wise Independence and Hard Boolean Functions. [Bibtex]

Andris Ambainis and Satyanarayana V. Lokam, Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function. [Bibtex]

David Fernández-Baca, Multi-parameter Minimum Spanning Trees. [Bibtex]

Ruy Luiz Milidiú and Eduardo Sany Laber, Linear Time Recognition of Optimal L-Restricted Prefix Codes (Extended Abstract). [Bibtex]

Jaroslav Opatrny, Uniform Multi-hop All-to-All Optical Routings in Rings. [Bibtex]

Serafino Cicerone, Gabriele Di Stefano, Daniele Frigioni and Umberto Nanni, A Fully Dynamic Algorithm for Distributed Shortest Paths. [Bibtex]

Andrew M. Odlyzko, Integer Factorization and Discrete Logarithms (Abstract). [Bibtex]

Igor Shparlinski, Communication Complexity and Fourier Coefficients of the Diffie-Hellman Key. [Bibtex]

Pedro Berrizbeitia, Mauricio Odreman Vera and Juan Tena Ayuso, Quintic Reciprocity and Primality Test for Numbers of the Form $M = A5^n\pm\omegan$. [Bibtex]

Matthias Krause and Hans-Ulrich Simon, Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography. [Bibtex]

Edward G. Coffman Jr., George S. Lueker, Joel Spencer and Peter M. Winkler, Average-Case Analysis of Rectangle Packings. [Bibtex]

Charles Knessl and Wojciech Szpankowski, Heights in Generalized Tries and PATRICIA Tries. [Bibtex]

Dominique Barth, Sylvie Corteel, Alain Denise, Danièle Gardy and Mario Valencia-Pabon, On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths. Extended Abstract. [Bibtex]

Joachim von zur Gathen and Thomas Lücking, Subresultants Revisited. [Bibtex]

Brigitte Vallée, A Unifying Framework for the Analysis of a Class of Euclidean Algorithms. [Bibtex]

Ali Akhavi, Worst-Case Complexity of the Optimal LLL Algorithm. [Bibtex]

Stephen L. Bloom and Zoltán Ésik, Iteration Algebras Are Not Finitely Axiomatizable. Extended Abstract. [Bibtex]

Richard Mayr, Undecidable Problems in Unreliable Computations. [Bibtex]

Claudio Gutiérrez, Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups. [Bibtex]

Marie-Pierre Béal, Olivier Carton, Christophe Prieur and Jacques Sakarovitch, Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers. [Bibtex]

Olivier Carton and Max Michel, Unambiguous Büchi Automata. [Bibtex]

Thomas Worsch, Linear Time Language Recognition on Cellular Automata with Restricted Communication. [Bibtex]

Luis R. Sierra Abbate, Pedro R. D'Argenio and Juan V. Echagüe, From Semantics to Spatial Distribution. [Bibtex]

Fran&;ois Laroussinie, Ph. Schnoebelen and M. Turuani, On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics. [Bibtex]

Maribel Fernández and Ian Mackie, A Theory of Operational Equivalence for Interaction Nets. [Bibtex]

Peter J. Grabner, Arnold Knopfmacher and Helmut Prodinger, Run Statistics for Geometrically Distributed Random Variables (Extended Abstract). [Bibtex]

Guy Louchard, Generalized Covariances of Multi-dimensional Brownian Excursion Local Times. [Bibtex]

Helmut Prodinger, Combinatorics of Geometrically Distributed Random Variables: Lenght of Ascending Runs. [Bibtex]



[Top] [Home] [LATIN 2000]



LATIN 1998


Daniel Panario and Alfredo Viola, Analysis of Rabin's Polynomial Irreducability Test. [Bibtex]

Peter Damaschke, A Chip Search Problem on Binary Numbers. [Bibtex]

Esteban Feuerstein, Uniform Service System with k Servers. [Bibtex]

David Fernández-Baca, Faster Non-linear Parametric Search with Applications to Optimazation and Dynamic Geometry. [Bibtex]

Frédérique Bassino, Marie-Pierre Béal and Dominique Perrin, Super-State Automata and Rational Trees. [Bibtex]

Nicolas Bedon and Olivier Carton, An Eilenberg Theorem for Words on Countable Ordinals. [Bibtex]

Alair Pereira do Lago, Maximal Groups in Free Burnside Semigroups. [Bibtex]

Jean-Eric Pin, Positive Varieties and Infinite Words. [Bibtex]

Marcos Peixoto Veloso and Laurent Fribourg, Unfolding Parametric Automata. [Bibtex]

Alain Finkel and Ph. Schnoebelen, Fundamental Structures in Well-Structured Infinite Transition Systems. [Bibtex]

Herbert Edelsbrunner, Shape Reconstruction with Delaunay Complex. [Bibtex]

Anamaria Gomide and Jorge Stolfi, Bases for Non-homogeneous Polynomial Ck Splines on the Sphere. [Bibtex]

Luerbio Faria, Celina M. Herrera de Figueiredo and Candido Ferreira Xavier de Mendon&;a Neto, The Splitting Number of the 4-Cube. [Bibtex]

James Abello and Emden R. Gansner, Short and Smooth Polygonal Paths. [Bibtex]

Gilles Brassard, Peter Høyer and Alain Tapp, Quantum Cryptanalysis of Hash and Claw-Free Functions. [Bibtex]

Mihir Bellare, Juan A. Garay and Tal Rabin, Batch Verification with Applications to Cryptography and Checking. [Bibtex]

Alejandro Hevia and Marcos Kiwi, Strength of Two Data Encryption Standard Implementations under Timing Attacks. [Bibtex]

Noga Alon, Spectral Techniques in Graph Algorithms. [Bibtex]

Michael Molloy and Bruce Reed, Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree. [Bibtex]

Orlando Lee and Yoshiko Wakabayashi, Circuit Covers in Series-Parallel Mixed Graphs. [Bibtex]

Elias Dahlhaus, A Linear Time Algorithm to Recognize Clustered Graphs and Its Parallelization. [Bibtex]

Klaus Jansen, A New Characterization for Parity Graphs and a Coloring Problem with Costs. [Bibtex]

Marisa Gutierrez and Joao Meidanis, On the Clique Operator. [Bibtex]

Andrei Z. Broder, Alan M. Frieze and Eli Upfal, Dynamic Packet Routing on Arrays with Bounded Buffers. [Bibtex]

Alan Roberts and Antonios Symvonis, On-Line Matching Routing on Trees. [Bibtex]

Dana Randall and Prasad Tetali, Analyzing Glauber Dynamics by Comparison of Markov Chains. [Bibtex]

Joachim von zur Gathen and Igor Shparlinski, The CREW PRAM Complexity of Modular Inversion. [Bibtex]

Friedhelm Meyer auf der Heide and Gabriel Terán Martinez, Communication-Efficient Parallel Multiway and Approximate Minimum Cut Computation. [Bibtex]

Richard Beigel and Egemen Tanin, The Geometry of Browsing. [Bibtex]

Ricardo Baeza-Yates and Gonzalo Navarro, Fast Two-Dimensional Approximate Pattern Matching. [Bibtex]

Gonzalo Navarro, Improved Approximate Pattern Matching on Hypertext. [Bibtex]

Claudio Gutiérrez, Solving Equations in Strings: On Makanin's Algorithm. [Bibtex]

Marie-France Sagot, Spelling Approximate Repeated or Common Motifs Using a Suffix Tree. [Bibtex]



[Top] [Home] [LATIN 1998]



LATIN 1995


James Abello and K. Kumar, Visibility Graphs of 2-Spiral Polygons. [Bibtex]

L. Alonso and R. Schott, Random Generation of Colored Trees. [Bibtex]

T. Asano, Desh Ranjan, T. Roos, E. Welzl and P. Widmayer, Space Filling Curves and Their Use in the Design of Geometric Data Structures. [Bibtex]

R. Balasubramanian, V. Raman and G. Srinivasaraghavan, Tight Bounds for Finding Degrees from the Adjacency Matrix. [Bibtex]

David A. M. Barrington and Howard Straubing, Lower Bounds for Modular Counting by Circuits with Modular Gates. [Bibtex]

B. Becker, R. Drechsler and R. Werchner, On the Relation Between BDDs and FDDs. [Bibtex]

F. Blanchard and A. Maass, On Dynamical Properties of Generalized Toggle Automata. [Bibtex]

Stephen L. Bloom and Zoltán Ésik, Free Shuffle Algebras in Language Varieties. [Bibtex]

P. G. Bradford, V. Choppella and G. J. E. Rawlins, Lower Bounds for the Matrix Chain Ordering Problem. [Bibtex]

S. Brands, Off-Line Electronic Cash Based on Secret-Key Certificates. [Bibtex]

Véronique Brùyere and G. Hansel, Recognizable Sets of Numbers in Nonstandard Bases. [Bibtex]

G. Buntrock and G. Niemann, On Weak Growing Context-Sensitive Grammars. [Bibtex]

B. R. Callejas Bedregal and B. M. Acioly, Logic of {P}lotkin Continuous Domain. [Bibtex]

S. Chaudhuri and D. Dubhashi, (Probabilistic) Recurrence Relations Revisited. [Bibtex]

Maxime Crochemore and Wojciech Rytter, On Linear-Time Alphabet-Independent 2-Dimensional Pattern Matching. [Bibtex]

J. O. Durand-Lose, Reversible Cellular Automaton Able to Simulate Any Other Reversible One Using Partitioning Automata. [Bibtex]

P. Eades and S. Whitesides, Nearest Neighbor Graph Realizability is NP-hard. [Bibtex]

David Fernandez-Baca and G. Slutzki, Linear-Time Algorithms for Parametric Minimum Spanning Tree Problems on Planar Graphs. [Bibtex]

Esteban Feuerstein, Paging More Than one Page. [Bibtex]

C. M. H. de Figueiredo, J. Meidanis and C. P. de Mello, On Edge-Colouring Indifference Graphs. [Bibtex]

G. Galbiati, A. Morzenti and F. Maffioli, On the Approximability of Some Maximum Spanning Tree Problems. [Bibtex]

S. Gao, Joachim von zur Gathen and Daniel Panario, Gauss Periods and Fast Exponentiation in Finite Fields. [Bibtex]

Williams I. Gasarch and Katia. S. Guimarães, Unbounded Search and Recursive Graph Problems. [Bibtex]

L. Gonzalez-Vega, On the Complexity of Computing the Greatest Common Divisor of Several Univariate Polynomials. [Bibtex]

J. Gruska, A. Monti, M. Napoli and D. Parente, State Complexity of SBTA Languages. [Bibtex]

C. Herzog, Pushdown Automata with Bounded Nondeterminism and Bounded Ambiguity. [Bibtex]

I. I. Macarie, Multihead Two-Way Probabilistic Finite Automata. [Bibtex]

M. Margenstern, Non-Erasing Turing Machines: A New Frontier Between a Decidable Halting Problem and Universality. [Bibtex]

Martín Matamala and Eric Goles, Cyclic Automata Networks on Finite Graphs. [Bibtex]

Joao Meidanis and J. C. Setubal, Multiple Alignment of Biological Sequences with Gap Flexibility. [Bibtex]

C. Meinel and S. Waack, Lower Bounds for the Modular Communication Complexity of Various Graph Accessibility Problems. [Bibtex]

M. Mundhenk, On Monotonous Oracle Machines. [Bibtex]

B. J. Oommen and E. V. de St. Croix, On Using Learning Automata for Fast Graph Partitioning. [Bibtex]

Helmut Prodinger, Solution of a Problem of Yekutieli and Mandelbrot. [Bibtex]

G. Richard and F. Saubion, A Rewrite Approach for Constraint Logic Programming. [Bibtex]

Z. Roka, Simulations Between Cellular Automata on Cayley Graphs. [Bibtex]

F. Wang, A Temporal Logic for Real-Time Partial-Ordering with Named Transactions. [Bibtex]

P. M. Yamakawa, H. Ebara and H. Nakano, A New Approach for Routing in Arrangement Graphs and Its Performance Evaluation. [Bibtex]



[Top] [Home] [LATIN 1995]



LATIN 1992


Paola Alimonti, Esteban Feuerstein and Umberto Nanni, Linear Time Algorithms for Liveness and Boundedness in Conflict-free Petri Nets. [Bibtex]

Jean-Paul Allouche, q-Regular Sequences and Other Generalizations of q-Automatic Sequences. [Bibtex]

David A. Mix Barrington and Howard Straubing, Complex Polynomials and Circuit Lower Bounds for Modular Counting. [Bibtex]

Danièle Beauquier, Michel Latteux and Karine Slowinski, A Decidability Result about Convex Polyominoes. [Bibtex]

Marshall W. Bern, Herbert Edelsbrunner, David Eppstein, S. Mitchell and Tio Seng Tan, Edge Insertion for Optional Triangulations. [Bibtex]

Saïd Bettayeb, Bin Cong, Mike Girou and Ivan Hal Sudborough, Simulation Permutation Networks on Hypercubes. [Bibtex]

Manuel Blum, Universal Statistical Tests. [Bibtex]

Francis Bossut and Bruno Warnin, Automata and Pattern Matching in Planar Directed Acyclic Graphs. [Bibtex]

Anne Brüggemann-Klein, Regular Expressions into Finite Automata. [Bibtex]

Véronique Bruyère, Automata and Codes with Bounded Deciphering Delay. [Bibtex]

Svante Carlsson and Jingsen Chen, Parallel Complexity of Heaps and Min-Max Heaps. [Bibtex]

Felipe Cucker and Francesc Rosselló, On the Complexity of Some Problems for the Blum, Shub \& Smale Model. [Bibtex]

Wenceslas Fernandez de la Vega, Vangelis Th. Paschos and Rachid Saad, Average Case Analysis of a Greedy Algorithm for the Minimum Hitting Set Problem. [Bibtex]

Afonso Ferreira and Siang W. Song, Achieving Optimality for Gate Matrix Layout and PLA Folding: a Graph Theoretic Approach. [Bibtex]

Christiane Frougny, How to Write Integers in Non-Integer Base. [Bibtex]

Oscar Garrido, Stefan Jarominek, Andrzej Lingas and Wojciech Rytter, A Simple Randomized Parallel Algorithm for Maximal f-Matching. [Bibtex]

William I. Gasarch and Katia S. Guimarães, On the Number Components of a Recursive Graph. [Bibtex]

Mark Giesbrecht, Factoring in Skew-Polynomial Rings. [Bibtex]

Joseph Gil and Yossi Matias, Leaders Election Without Conflict Resolution Rule - Fast and Efficient Randomized Simulations among CRCW PRAMs. [Bibtex]

Eric Goles and Marcos Kiwi, Dynamics of Sand-Piles Games on Graphs. [Bibtex]

Jaime Gutierrez and Tomás Recio, Rational Function Decomposition and Gröbner Bases in the Parameterization of Plane Curves (An extended abstract). [Bibtex]

Kosaburo Hashiguchi, The Double Reconstruction Conjectures about Colored Hypergraphs and Colored Directed Graphs. [Bibtex]

Ulrich Hertrampf, Locally Definable Acceptance Types - The Three-Valued Case. [Bibtex]

Joachim Hollman, On the Computation of the Hilbert Series. [Bibtex]

Esther Jennings and Lenka Motyckova, A Distributed Algorithm for finding All Maximal Cliques in a Network Graph. [Bibtex]

Erich Kaltofen, Polynomial Factorization 1987-1991. [Bibtex]

Nami Kobayashi, Properties of Recognizable M-Subsets of a Free Monoid. [Bibtex]

Alair Pereira do Lago, On the Burnside Semigroups xn = xn+m. [Bibtex]

Arjen K. Lenstra, Massively Parallel Computing and Factoring. [Bibtex]

Aldo de Luca and Stefano Varricchio, Some Regularity Conditions Based on Well Quasi-Orders. [Bibtex]

Gene Myers, Approximate Matching of Network Expressions with Spacers. [Bibtex]

Rolf Niedermeier and Peter Rossmanith, Unambiguous Simulations of Auxiliary Pushdown Automata and Circuits (Extended Abstract). [Bibtex]

Jean-Eric Pin, On Reversible Automata. [Bibtex]

Oscar Porto, Even Induced Cycles in Planar Graphs. [Bibtex]

Vaughan R. Pratt, Arithmetic + Logic + Geometry = Concurrency. [Bibtex]

José D. P. Rolim, On the Density and Core of the Complexity Classes. [Bibtex]

Jacques Sakarovitch, The "Last" Decision Problem for Rational Trace Languages. [Bibtex]

Alistair Sinclair, Improved Bounds for Mixing Rates of Marked Chains and Multicommodity Flow. [Bibtex]

Daniel Dominic Sleator, Data Structures and Terminating Petri Nets. [Bibtex]

Denis Thérien, Circuits Constructed with MODq Gates Cannot Compute AND in Sublinear Size. [Bibtex]

Andreas Weber, Decomposing a k-valued Transducer into k Unambiguous Ones. [Bibtex]

Xiao Zhou, Shin-Ichi Nakano, Hitoshi Suzuki and Takao Nishizeki, An Efficient Algorithm for Edge-Coloring Series-Parallel Multigraphs. [Bibtex]

Michel Cosnard, Pascal Koiran and Hélène Paugam-Moisy, Complexity Issues in Neural Network Computations. [Bibtex]



[Top] [Home] [LATIN 1992]