____  __
  ______     _______

LATIN 2022

Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai and Hao-Tsung Yang, Obtaining Approximately Optimal and Diverse Solutions via Dispersion. [Bibtex]

Giulia Bernardini, Estéban Gabory, Solon P. Pissis, Leen Stougie, Michelle Sweering and Wiktor Zuba, Elastic-Degenerate String Matching with 1 Error. [Bibtex]

Jiehua Chen, Martin Nöllenburg, Sofia Simola, Anaïs Villedieu and Markus Wallinger, Multidimensional Manhattan Preferences. [Bibtex]

Ramtin Afshar and Michael T. Goodrich, Exact Learning of Multitrees and Almost-Trees Using Path Queries. [Bibtex]

José D. Alvarado, Lucas Colucci, Roberto Parente and Victor Souza, On the Zero-Sum Ramsey Problem over \(\mathbb{Z}_2^d\). [Bibtex]

Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep and R. Subashini, Cutting a Tree with Subgraph Complementation is Hard, Except for Some Small Trees. [Bibtex]

Saman Bazargani, Ahmad Biniaz and Prosenjit Bose, Piercing Pairwise Intersecting Convex Shapes in the Plane. [Bibtex]

Luca Becchetti, Andrea E. F. Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan and Isabella Ziccardi, Percolation and Epidemic Processes in One-Dimensional Small-World Networks - (Extended Abstract). [Bibtex]

Marcelo Pinheiro Leite Benedito, Lucas P. Melo and Lehilton L. C. Pedrosa, A Parameterized Approximation Algorithm for the Multiple Allocation \(k\)-Hub Center. [Bibtex]

Sriram Bhyravarapu, Satyabrata Jana, Fahad Panolan, Saket Saurabh and Shaily Verma, List Homomorphism: Beyond the Known Boundaries. [Bibtex]

Olivier Bodini, Antoine Genitrini and Mehdi Naima, A Combinatorial Link Between Labelled Graphs and Increasingly Labelled Schröder Trees. [Bibtex]

Jan Bok, Richard C. Brewster, Pavol Hell, Nikola Jedlicková and Arash Rafiey, Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs. [Bibtex]

Nicolas Bonichon, Prosenjit Bose and Yan Garito, Local Routing Algorithms on Euclidean Spanners with Small Diameter. [Bibtex]

Prosenjit Bose, Jean-Lou De Carufel and Thomas C. Shermer, On the Zombie Number of Various Graph Classes. [Bibtex]

Nader H. Bshouty, Almost Optimal Proper Learning and Testing Polynomials. [Bibtex]

Claude Carlet, On APN Functions Whose Graphs are Maximal Sidon Sets. [Bibtex]

David Casas and Mikhail V. Volkov, Binary Completely Reachable Automata. [Bibtex]

Prasad Chaugule and Nutan Limaye, On the Closures of Monotone Algebraic Classes and Variants of the Determinant. [Bibtex]

Julien Courtiel, Paul Dorbec and Romain Lecoq, Theoretical Analysis of git bisect. [Bibtex]

Vasco Cruz and Ana Paula Tomás, On \(r\)-Guarding SCOTs - A New Family of Orthogonal Polygons. [Bibtex]

Arun Kumar Das, Sandip Das, Guilherme Dias da Fonseca, Yan Gerard and Bastien Rivier, Complexity Results on Untangling Red-Blue Matchings. [Bibtex]

Thomas Dissaux and Nicolas Nisse, Pathlength of Outerplanar Graphs. [Bibtex]

Amalia Duch, Conrado Martínez, Mercè Pons and Salvador Roura, Median and Hybrid Median \(K\)-Dimensional Trees. [Bibtex]

Andrzej Dudek, Jaroslaw Grytczuk and Andrzej Rucinski, Patterns in Ordered (random) Matchings. [Bibtex]

Cristina G. Fernandes, Carla Negri Lintzmayer and Phablo F. S. Moura, Approximations for the Steiner Multicycle Problem. [Bibtex]

François Le Gall and Daiki Suruga, Bounds on Oblivious Multiparty Quantum Communication Complexity. [Bibtex]

Waldo Gálvez and Víctor Verdugo, Approximation Schemes for Packing Problems with \(\ell_p\)-norm Diversity Constraints. [Bibtex]

Matt Gibson-Lopez, Erik Krohn, Bengt J. Nilsson, Matthew Rayford, Sean Soderman and Pawel Zylinski, On Vertex Guarding Staircase Polygons. [Bibtex]

Ludmila Glinskih and Artur Riazanov, MCSP is Hard for Read-Once Nondeterministic Branching Programs. [Bibtex]

Guilherme C. M. Gomes, Bruno Porto Masquio, Paulo E. D. Pinto, Vinicius F. dos Santos and Jayme Luiz Szwarcfiter, Weighted Connected Matchings. [Bibtex]

Renzo Gómez, Flávio Keidi Miyazawa and Yoshiko Wakabayashi, Tree 3-Spanners on Generalized Prisms of Graphs. [Bibtex]

Viktor Henriksson and Manfred Kufleitner, Conelikes and Ranker Comparisons. [Bibtex]

Félix Hernández and Gerardo Vega, On the Subfield Codes of a Subclass of Optimal Cyclic Codes and Their Covering Structures. [Bibtex]

Hannah Miller Hillberg, Erik Krohn and Alex Pahlow, On the Complexity of Half-Guarding Monotone Polygons. [Bibtex]

Seungbum Jo and Geunho Kim, Space-Efficient Data Structure for Next/Previous Larger/Smaller Value Queries. [Bibtex]

Tomasz Kociumaka, Gonzalo Navarro and Francisco Olivares, Near-Optimal Search Time in \(\delta\)-Optimal Space. [Bibtex]

Alane M. de Lima, Murilo V. G. da Silva and André Luís Vignatti, Estimating the Clustering Coefficient Using Sample Complexity Analysis. [Bibtex]

Sylvain Lombardy and Jacques Sakarovitch, The Net Automaton of a Rational Expression. [Bibtex]

Caroline Mattes and Armin Weiß, Improved Parallel Algorithms for Generalized Baumslag Groups. [Bibtex]

Augusto Modanese and Thomas Worsch, Embedding Arbitrary Boolean Circuits into Fungal Automata. [Bibtex]

Charis Papadopoulos and Athanasios E. Zisis, Computing and Listing Avoidable Vertices and Paths. [Bibtex]

Thomas Place and Marc Zeitoun, How Many Times Do You Need to Go Back to the Future in Unary Temporal Logic?. [Bibtex]

Carole Porrier and Thomas Fernique, A General Approach to Ammann Bars for Aperiodic Tilings. [Bibtex]

Antonio Restivo, Giuseppe Romana and Marinella Sciortino, String Attractors and Infinite Words. [Bibtex]

Caroline Aparecida de Paula Silva, Cândida Nunes da Silva and Orlando Lee, On \(\chi\)-Diperfect Digraphs with Stability Number Two. [Bibtex]

Thore Thießen and Jan Vahrenhold, Klee's Measure Problem Made Oblivious. [Bibtex]

[Top] [Home] [LATIN 2022]

LATIN 2020

Julien Clément and Antoine Genitrini, Binary Decision Diagrams: From Tree Compaction to Sampling. [Bibtex]

Sancrey Rodrigues Alves, Fernanda Couto, Luérbio Faria, Sylvain Gravier, Sulamita Klein and Uéverton S. Souza, Graph Sandwich Problem for the Property of Being Well-Covered and Partitionable into \(k\) Independent Sets and \(\ell\) Cliques. [Bibtex]

Bertie Ancona, Ayesha Bajwa, Nancy A. Lynch and Frederik Mallmann-Trenn, How to Color a French Flag - Biologically Inspired Algorithms for Scale-Invariant Patterning. [Bibtex]

Ny Aina Andriambolamalala and Vlady Ravelomanana, Transmitting once to Elect a Leader on Wireless Networks. [Bibtex]

Elena Arseneva, Prosenjit Bose, Pilar Cano and Rodrigo I. Silveira, Flips in Higher Order Delaunay Triangulations. [Bibtex]

Chen Avin, Kaushik Mondal and Stefan Schmid, Dynamically Optimal Self-adjusting Single-Source Tree Networks. [Bibtex]

Costin Badescu and Ryan O'Donnell, Lower Bounds for Testing Complete Positivity and Quantum Separability. [Bibtex]

Gill Barequet and Gil Ben-Shachar, On Minimal-Perimeter Lattice Animals. [Bibtex]

Gill Barequet and Mira Shalah, Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes. [Bibtex]

Frank Bauernöppel, Anil Maheshwari and Jörg-Rüdiger Sack, An \(\Omega(n^3)\) Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-Dimensional Polyhedral Structures. [Bibtex]

Michael A. Bender, Mayank Goswami, Dzejla Medjedovic, Pablo Montes and Kostas Tsichlas, Batched Predecessor and Sorting with Size-Priced Information in External Memory. [Bibtex]

Louisa Seelbach Benkner and Stephan G. Wagner, On the Collection of Fringe Subtrees in Random Binary Trees. [Bibtex]

Sergey Bereg, Computing Balanced Convex Partitions of Lines. [Bibtex]

Jean R. S. Blair, Pinar Heggernes, Paloma T. Lima and Daniel Lokshtanov, On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number. [Bibtex]

Ivan Bliznets and Danil Sagunov, Maximizing Happiness in Graphs of Bounded Clique-Width. [Bibtex]

Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniël Paulusma and Erik Jan van Leeuwen, Steiner Trees for Hereditary Graph Classes. [Bibtex]

Miklós Bóna, A Method to Prove the Nonrationality of Some Combinatorial Generating Functions. [Bibtex]

Anthony Bonato, Konstantinos Georgiou, Calum MacRury and Pawel Pralat, Probabilistically Faulty Searching on a Half-Line - (Extended Abstract). [Bibtex]

Kevin Buchin, Dmitry Kosolobov, Willem Sonke, Bettina Speckmann and Kevin Verbeek, Ordered Strip Packing. [Bibtex]

Jaroslaw Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase and Sumedha Uniyal, PTAS for Steiner Tree on Map Graphs. [Bibtex]

Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov and Luca Trevisan, Lower Bounds for Max-Cut via Semidefinite Programming. [Bibtex]

Bruno Pasqualotto Cavalar, Mrinal Kumar and Benjamin Rossman, Monotone Circuit Lower Bounds from Robust Sunflowers. [Bibtex]

Steven Chaplick, Magnús M. Halldórsson, Murilo Santos de Lima and Tigran Tonoyan, Query Minimization Under Stochastic Uncertainty. [Bibtex]

Siddhesh Chaubal and Anna Gál, Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions. [Bibtex]

Rami Daknama, Konstantinos Panagiotou and Simon Reisser, Asymptotics for Push on the Complete Graph. [Bibtex]

Stefan S. Dantchev, Abdul Ghani and Barnaby Martin, Sherali-Adams and the Binary Encoding of Combinatorial Principles. [Bibtex]

Zakir Deniz, Simon Nivelle, Bernard Ries and David Schindl, On Some Subclasses of Split \(B_1\)-EPG Graphs. [Bibtex]

Ran Duan, Haoqing He and Tianyi Zhang, Near-Linear Time Algorithm for Approximate Minimum Degree Spanning Trees. [Bibtex]

Khaled M. Elbassioni, Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations. [Bibtex]

Vincent Fagnon, Imed Kacem, Giorgio Lucarelli and Bertrand Simon, Scheduling on Hybrid Platforms: Improved Approximability Window. [Bibtex]

Cristina G. Fernandes and Carla Negri Lintzmayer, Leafy Spanning Arborescences in DAGs. [Bibtex]

Petr A. Golovach, R. Krithika, Abhishek Sahu, Saket Saurabh and Meirav Zehavi, Graph Hamiltonicity Parameterized by Proper Interval Deletion Set. [Bibtex]

Petr A. Golovach, Paloma T. Lima and Charis Papadopoulos, Graph Square Roots of Small Distance from Degree One Graphs. [Bibtex]

Guilherme de C. M. Gomes, Matheus R. Guedes and Vinicius F. dos Santos, Structural Parameterizations for Equitable Coloring. [Bibtex]

Marina Groshaus, André Luiz Pires Guedes and Fabricio Schiavon Kolberg, On the Helly Subclasses of Interval Bigraphs and Circular Arc Bigraphs. [Bibtex]

Hiệp Hàn, Marcos Kiwi and Matías Pavez-Signé, Quasi-Random Words and Limits of Word Sequences. [Bibtex]

Shunsuke Inenaga, Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries. [Bibtex]

Mincheol Kim, Sang Duk Yoon and Hee-Kap Ahn, Shortest Rectilinear Path Queries to Rectangles in a Rectangular Domain. [Bibtex]

Tomasz Kociumaka, Gonzalo Navarro and Nicola Prezza, Towards a Definitive Measure of Repetitiveness. [Bibtex]

Ioannis Mantas, Evanthia Papadopoulou, Vera Sacristán and Rodrigo I. Silveira, Farthest Color Voronoi Diagrams: Complexity and Algorithms. [Bibtex]

Thiago Marcilon, Nícolas A. Martins and Rudini Menezes Sampaio, Hardness of Variants of the Graph Coloring Game. [Bibtex]

Ido Nachum and Amir Yehudayoff, On Symmetry and Initialization for Neural Networks. [Bibtex]

Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki and Yuki Ubukata, . [Bibtex]

Lehilton L. C. Pedrosa and Greis Y. O. Quesquén, Approximating Routing and Connectivity Problems with Multiple Distances. [Bibtex]

Lehilton L. C. Pedrosa and Hugo Kooki Kasuya Rosado, A 2-Approximation for the \(k\)-Prize-Collecting Steiner Tree Problem. [Bibtex]

Pablo Pérez-Lantero, Carlos Seara and Jorge Urrutia, Rectilinear Convex Hull of Points in 3D. [Bibtex]

Md Lutfar Rahman and Thomas Watson, Tractable Unordered 3-CNF Games. [Bibtex]

Andrew Read-McFarland and Daniel Stefankovic, The Hardness of Sampling Connected Subgraphs. [Bibtex]

Benjamin Rossman, Thresholds in the Lattice of Subspaces of \(\mathbb{F}_q^n\). [Bibtex]

Kazuya Shimizu and Ryuhei Mori, Exponential-Time Quantum Algorithms for Graph Coloring Problems. [Bibtex]

[Top] [Home] [LATIN 2020]

LATIN 2018

Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu, Satyanarayana V. Lokam and Nitin Saurabh, Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions. [Bibtex]

Meng He, Cuong P. Nguyen and Norbert Zeh, Maximal and Convex Layers of Random Point Sets. [Bibtex]

R. Krithika, Abhishek Sahu, Saket Saurabh and Meirav Zehavi, . [Bibtex]

Alexandre Santiago de Abreu, Luís Felipe I. Cunha, Tharso D. Fernandes, Celina M. H. de Figueiredo, Luis Antonio Brasil Kowada, Franklin L. Marquezino, Daniel Posner and Renato Portugal, . [Bibtex]

Kunal Agrawal, Jing Li, Kefu Lu and Benjamin Moseley, Scheduling Parallelizable Jobs Online to Maximize Throughput. [Bibtex]

Nir Ailon, Anup Bhattacharya and Ragesh Jaiswal, Approximate Correlation Clustering Using Same-Cluster Queries. [Bibtex]

Peter Allen, Christoph Koch, Olaf Parczyk and Yury Person, Finding Tight Hamilton Cycles in Random Hypergraphs Faster. [Bibtex]

Saeed Akhoondian Amiri, Klaus-Tycho Foerster and Stefan Schmid, Walking Through Waypoints. [Bibtex]

Antonios Antoniadis, Carsten Fischer and Andreas Tönnis, A Collection of Lower Bounds for Online Matching on the Line. [Bibtex]

Júlio Araújo, Victor A. Campos, Ana Karolinna Maia, Ignasi Sau and Ana Silva, . [Bibtex]

Sandip Banerjee, Sujoy Bhore and Rajesh Chitnis, . [Bibtex]

Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh, A Polynomial Sized Kernel for Tracking Paths Problem. [Bibtex]

Bahareh Banyassady, Luis Barba and Wolfgang Mulzer, Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees. [Bibtex]

Yair Bartal and Lee-Ad Gottlieb, Approximate Nearest Neighbor Search for \(\ell_p\)-Spaces \(2\lt p\lt\infty \) via Embeddings. [Bibtex]

Florent Becker, Pedro Montealegre, Ivan Rapaport and Ioan Todinca, . [Bibtex]

Therese C. Biedl, Martin Derka, Veronika Irvine, Anna Lubiw, Debajyoti Mondal and Alexi Turcotte, Partitioning Orthogonal Histograms into Rectangular Boxes. [Bibtex]

Lélia Blin and Sébastien Tixeuil, Compact Self-Stabilizing Leader Election for General Networks. [Bibtex]

Lucas Boczkowski, Brieuc Guinard, Amos Korman, Zvi Lotker and Marc P. Renault, Random Walks with Multiple Step Lengths. [Bibtex]

Jean-Daniel Boissonnat, Kunal Dutta, Arijit Ghosh and Sudeshna Kolay, Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set. [Bibtex]

Bartlomiej Bosek, Dariusz Leniowski, Piotr Sankowski and Anna Zych-Pawlewicz, A Tight Bound for Shortest Augmenting Paths on Trees. [Bibtex]

Thomas Bosman, Martijn van Ee, Yang Jiao, Alberto Marchetti-Spaccamela, R. Ravi and Leen Stougie, . [Bibtex]

Luis Evaristo Caraballo, Pablo Pérez-Lantero, Carlos Seara and Inmaculada Ventura, Maximum Box Problem on Stochastic Points. [Bibtex]

Rodrigo A. Carrasco, Kirk Pruhs, Cliff Stein and José Verschae, The Online Set Aggregation Problem. [Bibtex]

Thom Castermans, Bettina Speckmann, Frank Staals and Kevin Verbeek, Agglomerative Clustering of Growing Squares. [Bibtex]

L. Sunil Chandran, Anita Das, Davis Issac and Erik Jan van Leeuwen, Algorithms and Bounds for Very Strong Rainbow Coloring. [Bibtex]

Panagiotis Charalampopoulos, Costas S. Iliopoulos, Chang Liu and Solon P. Pissis, Property Suffix Array with Applications. [Bibtex]

Vincent Chau, Shengzhong Feng and Nguyen Kim Thang, Competitive Algorithms for Demand Response Management in Smart Grid. [Bibtex]

Ruiwen Chen, Igor Carboni Oliveira and Rahul Santhanam, An Average-Case Lower Bound Against \(\mathsf{ACC}^0\). [Bibtex]

Anders Roy Christiansen and Mikko Berggren Ettienne, Compressed Indexing with Signature Grammars. [Bibtex]

Jonas Cleve and Wolfgang Mulzer, Combinatorics of Beacon-Based Routing in Three Dimensions. [Bibtex]

Zakir Deniz, Simon Nivelle, Bernard Ries and David Schindl, On Split \(B_1\)-EPG Graphs. [Bibtex]

Tamal K. Dey, Tianqi Li and Yusu Wang, Efficient Algorithms for Computing a Minimal Homology Basis. [Bibtex]

Sergey Dovgal and Vlady Ravelomanana, . [Bibtex]

Philippe Duchon and Cyril Nicaud, On the Biased Partial Word Collector Problem. [Bibtex]

Andrzej Dudek and Andrzej Ruciński, Constructive Ramsey Numbers for Loose Hyperpaths. [Bibtex]

Matteo Dusefante and Riko Jacob, Cache Oblivious Sparse Matrix Multiplication. [Bibtex]

David Eppstein, Michael T. Goodrich and Nil Mamano, Reactive Proximity Data Structures for Graphs. [Bibtex]

Sándor P. Fekete, Sven von Höveling, Joseph S. B. Mitchell, Christian Rieck, Christian Scheffer, Arne Schmidt and James R. Zuber, Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading. [Bibtex]

Carsten Fischer and Heiko Röglin, Probabilistic Analysis of Online (Class-Constrained) Bin Packing and Bin Covering. [Bibtex]

Martin Fürer, Carlos Hoppen, David Pokrass Jacobs and Vilmar Trevisan, Locating the Eigenvalues for Graphs of Small Clique-Width. [Bibtex]

Travis Gagie, Gonzalo Navarro and Nicola Prezza, On the Approximation Ratio of Lempel-Ziv Parsing. [Bibtex]

Hang Gao and Wenyu Gao, Kernelization for Maximum Happy Vertices Problem. [Bibtex]

Bernd Gärtner and Ahad N. Zehmakan, Majority Model on Random Regular Graphs. [Bibtex]

Serge Gaspers, Joachim Gudmundsson, Michael Horton and Stefan Rümmele, When is Red-Blue Nonblocker Fixed-Parameter Tractable?. [Bibtex]

Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis, Incremental Strong Connectivity and 2-Connectivity in Directed Graphs. [Bibtex]

Roberto Grossi, Andrea Marino and Luca Versari, Efficient Algorithms for Listing k Disjoint st-Paths in Graphs. [Bibtex]

Juan Gutiérrez, Transversals of Longest Cycles in Chordal and Bounded Tree-Width Graphs. [Bibtex]

Jie Han, Yoshiharu Kohayakawa, Marcelo Tadeu Sales and Henrique Stagni, Property Testing for Point Sets on the Plane. [Bibtex]

Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi and Ravi Sundaram, Plane Gossip: Approximating Rumor Spread in Planar Graphs. [Bibtex]

Adalat Jabrayilov and Petra Mutzel, New Integer Linear Programming Models for the Vertex Coloring Problem. [Bibtex]

Yasushi Kawase, Hanna Sumita and Takuro Fukunaga, Submodular Maximization with Uncertain Knapsack Capacity. [Bibtex]

Samir Khuller, Jingling Li, Pascal Sturmfels, Kevin Sun and Prayaag Venkat, Select and Permute: An Improved Online Framework for Scheduling to Minimize Weighted Completion Time. [Bibtex]

Katharina Klost and Wolfgang Mulzer, . [Bibtex]

Yoshiharu Kohayakawa, Flávio Keidi Miyazawa and Yoshiko Wakabayashi, . [Bibtex]

Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny and Sunil M. Shende, Satisfying Neighbor Preferences on a Circle. [Bibtex]

Carla Negri Lintzmayer, Flávio Keidi Miyazawa and Eduardo Candido Xavier, Two-Dimensional Knapsack for Circles. [Bibtex]

Themistoklis Melissourgos, Sotiris E. Nikoletseas, Christoforos Raptopoulos and Paul G. Spirakis, . [Bibtex]

Wouter Meulemans, Bettina Speckmann, Kevin Verbeek and Jules Wulms, . [Bibtex]

Sarah Miracle and Amanda Pascoe Streib, Rapid Mixing of \(k\)-Class Biased Permutations. [Bibtex]

Torrie L. Nichols, Alexander Pilz, Csaba D. Tóth and Ahad N. Zehmakan, Transition Operations over Plane Trees. [Bibtex]

Pablo Rotondo, Brigitte Vallée and Alfredo Viola, Analysis of the Continued Logarithm Algorithm. [Bibtex]

Daniel Stefankovic, Eric Vigoda and John Wilmes, On Counting Perfect Matchings in General Graphs. [Bibtex]

Thomas Watson, Quadratic Simulations of Merlin-Arthur Games. [Bibtex]

[Top] [Home] [LATIN 2018]

LATIN 2016

Akanksha Agrawal, Sudeshna Kolay, Daniel Lokshtanov and Saket Saurabh, A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion. [Bibtex]

Hee-Kap Ahn, Helmut Alt, Maike Buchin, Eunjin Oh, Ludmila Scharf and Carola Wenk, A Middle Curve Based on Discrete Fréchet Distance. [Bibtex]

Kamal Al-Bawani, Matthias Englert and Matthias Westermann, Comparison-Based FIFO Buffer Management in QoS Switches. [Bibtex]

Susanne Albers, Evripidis Bampis, Dimitrios Letsios, Giorgio Lucarelli and Richard Stotz, Scheduling on Power-Heterogeneous Processors. [Bibtex]

Amihood Amir, Mika Amit, Gad M. Landau and Dina Sokol, Period Recovery over the Hamming and Edit Distances. [Bibtex]

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior and Michele Scquizzato, Chasing Convex Bodies and Functions. [Bibtex]

N. R. Aravind, R. B. Sandeep and Naveen Sivadasan, Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems. [Bibtex]

Pradeesha Ashok, Sudeshna Kolay and Saket Saurabh, Parameterized Complexity of Red Blue Set Cover for Lines. [Bibtex]

Sang Won Bae, Chan-Su Shin and Antoine Vigneron, Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons. [Bibtex]

Evangelos Bampas and David Ilcinkas, On Mobile Agent Verifiable Problems. [Bibtex]

Indranil Banerjee and Dana Richards, Computing Maximal Layers of Points in Ef(n). [Bibtex]

Michael A. Bekos, Michael Kaufmann and Robert Krug, On the Total Number of Bends for Planar Octilinear Drawings. [Bibtex]

Djamal Belazzougui, Travis Gagie, Veli Mäkinen, Marco Previtali and Simon J. Puglisi, Bidirectional Variable-Order de Bruijn Graphs. [Bibtex]

Fernando Benavides and Sergio Rajsbaum, The Read/Write Protocol Complex Is Collapsible. [Bibtex]

Michael A. Bender, Rezaul Chowdhury, Alexander Conway, Martin Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon and Shikha Singh, The I/O Complexity of Computing Prime Tables. [Bibtex]

Olivier Bodini, Matthieu Dien, Xavier Fontaine, Antoine Genitrini and Hsien-Kuei Hwang, Increasing Diamonds. [Bibtex]

Katerina Böhmová, Yann Disser, Matús Mihalák and Rastislav Srámek, Scheduling Transfers of Resources over Time: Towards Car-Sharing with Flexible Drop-Offs. [Bibtex]

Édouard Bonnet, Bruno Escoffier, Vangelis Th. Paschos and Georgios Stamoulis, A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs. [Bibtex]

Prosenjit Bose, Darryl Hill and Michiel H. M. Smid, Improved Spanning Ratio for Low Degree Plane Spanners. [Bibtex]

Iffat Chowdhury and Matt Gibson, Constructing Consistent Digital Line Segments. [Bibtex]

Marek Chrobak and Kevin P. Costello, Faster Information Gathering in Ad-Hoc Radio Tree Networks. [Bibtex]

Mercè Claverol, Elena Khramtcova, Evanthia Papadopoulou, Maria Saumell and Carlos Seara, Stabbing Circles for Sets of Segments in the Plane. [Bibtex]

Manfred Cochefert, Jean-François Couturier, Serge Gaspers and Dieter Kratsch, Faster Algorithms to Enumerate Hypergraph Transversals. [Bibtex]

Alessio Conte, Roberto Grossi, Andrea Marino and Romeo Rizzi, Listing Acyclic Orientations of Graphs with Single and Multiple Sources. [Bibtex]

Maxime Crochemore, Gabriele Fici, Robert Mercas and Solon P. Pissis, Linear-Time Sequence Comparison Using Minimal Absent Words & Applications. [Bibtex]

Patrick Baxter Dragon, Oscar I. Hernandez and Aaron Williams, The Grandmama de Bruijn Sequence for Binary Strings. [Bibtex]

Pål Grønås Drange, Markus S. Dregi and R. B. Sandeep, Compressing Bounded Degree Graphs. [Bibtex]

Amalia Duch, Gustavo Lau and Conrado Martínez, Random Partial Match in Quad-\(K\)-d Trees. [Bibtex]

David Eppstein and Daniel S. Hirschberg, From Discrepancy to Majority. [Bibtex]

David Eppstein, Philipp Kindermann, Stephen G. Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides and Stephen K. Wismath, On the Planar Split Thickness of Graphs. [Bibtex]

Hossein Esfandiari and Guy Kortsarz, A Bounded-Risk Mechanism for the Kidney Exchange Game. [Bibtex]

Martin Farach-Colton and Meng-Tsung Tsai, Tight Approximations of Degeneracy in Large Graphs. [Bibtex]

Cristina G. Fernandes, Samuel P. de Paula and Lehilton L. C. Pedrosa, Improved Approximation Algorithms for Capacitated Fault-Tolerant \(k\)-Center. [Bibtex]

Martin Fink, John Hershberger, Subhash Suri and Kevin Verbeek, Bundled Crossings in Embedded Graphs. [Bibtex]

Carsten Fischer and Heiko Röglin, Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering. [Bibtex]

Johannes Fischer, Tomohiro I. and Dominik Köppl, Deterministic Sparse Suffix Sorting on Rewritable Texts. [Bibtex]

Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers, Minimizing the Number of Opinions for Fault-Tolerant Distributed Decision Using Well-Quasi Orderings. [Bibtex]

Samuele Giraudo and Stéphane Vialette, Unshuffling Permutations. [Bibtex]

Nicholas J. A. Harvey and Keyulu Xu, Generating Random Spanning Trees via Fast Matrix Multiplication. [Bibtex]

Haim Kaplan, Wolfgang Mulzer, Liam Roditty and Paul Seiferth, Routing in Unit Disk Graphs. [Bibtex]

Kolja Knauer and Bartosz Walczak, Graph Drawings with One Bend and Few Slopes. [Bibtex]

Michal Kotrbcík, Rastislav Královic and Sebastian Ordyniak, Edge-Editing to a Dense and a Sparse Graph Class. [Bibtex]

Nirman Kumar and Subhash Suri, Containment and Evasion in Stochastic Point Data. [Bibtex]

Moses Ganardi, Danny Hucke, Markus Lohrey and Eric Noeth, Tree Compression Using String Grammars. [Bibtex]

Victor Marsault and Jacques Sakarovitch, Trees and Languages with Periodic Signature. [Bibtex]

Syed Mohammad Meesum and Saket Saurabh, Rank Reduction of Directed Graphs by Vertex and Edge Deletions. [Bibtex]

Matthias Mnich, Heiko Röglin and Clemens Rösner, New Deterministic Algorithms for Solving Parity Games. [Bibtex]

Eunjin Oh, Sang Won Bae and Hee-Kap Ahn, Computing a Geodesic Two-Center of Points in a Simple Polygon. [Bibtex]

Alice Paul, Matthias Poloczek and David P. Williamson, Simple Approximation Algorithms for Balanced MAX 2SAT. [Bibtex]

Ashutosh Rai, M. S. Ramanujan and Saket Saurabh, A Parameterized Algorithm for Mixed-Cut. [Bibtex]

Saket Saurabh and Meirav Zehavi, \((k, n-k)\)-Max-Cut: An \(O^*(2p)\)-Time Algorithm and a Polynomial Kernel. [Bibtex]

Andreas Wiese, Independent Set of Convex Polygons: From \(n^\epsilon\) to \(1+\epsilon\) via Shrinking. [Bibtex]

[Top] [Home] [LATIN 2016]

LATIN 2014

Volker Diekert, Alexei G. Myasnikov and Armin Weiß, Conjugacy in Baumslag's Group, Generic Case Complexity, and Division in Power Circuits. [Bibtex]

Hélio B. Macêdo Filho, Raphael C. S. Machado and Celina M. H. de Figueiredo, Hierarchical Complexity of 2-Clique-Colouring Weakly Chordal Graphs and Perfect Graphs Having Cliques of Size at Least 3. [Bibtex]

Michael Lampis and Valia Mitsou, The Computational Complexity of the Game of Set and Its Theoretical Applications. [Bibtex]

José R. Correa, Laurent Feuilloley and José A. Soto, Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line. [Bibtex]

Nikhil Bansal, Tjark Vredeveld and Ruben van der Zwaan, Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. [Bibtex]

Anja Rey and Jörg Rothe, False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time. [Bibtex]

Martin Fürer, A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width. [Bibtex]

Luis Barba, Prosenjit Bose and Stefan Langerman, Optimal Algorithms for Constrained 1-Center Problems. [Bibtex]

Panagiotis Cheilaris, Elena Khramtcova, Stefan Langerman and Evanthia Papadopoulou, A Randomized Incremental Approach for the Hausdorff Voronoi Diagram of Non-crossing Clusters. [Bibtex]

Prosenjit Bose and André van Renssen, Upper Bounds on the Spanning Ratio of Constrained Theta-Graphs. [Bibtex]

Sang-Won Bae, Matias Korman, Yoshio Okamoto and Haitao Wang, Computing the \(L_1\) Geodesic Diameter and Center of a Simple Polygon in Linear Time. [Bibtex]

Emilio Di Giacomo, Giuseppe Liotta and Fabrizio Montecchiani, The Planar Slope Number of Subcubic Graphs. [Bibtex]

Muhammad Jawaherul Alam, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov and Alexander Wolff, Smooth Orthogonal Drawings of Planar Graphs. [Bibtex]

Stephane Durocher, Stefan Felsner, Saeed Mehrabi and Debajyoti Mondal, Drawing \(HV\)-Restricted Planar Graphs. [Bibtex]

Luca Castelli Aleardi, Éric Fusy and Anatolii Kostrygin, Periodic Planar Straight-Frame Drawings with Polynomial Resolution. [Bibtex]

Ines Klimann and Matthieu Picantin, A Characterization of Those Automata That Structurally Generate Finite Groups. [Bibtex]

Mikhail Barash and Alexander Okhotin, Linear Grammars with One-Sided Contexts and Their Automaton Representation. [Bibtex]

Edward Hermann Haeusler and Mauricio Ayala-Rincón, On the Computability of Relations on \(\lambda\)-Terms and Rice's Theorem - The Case of the Expansion Problem for Explicit Substitutions. [Bibtex]

Maurice Herlihy, Sergio Rajsbaum, Michel Raynal and Julien Stainer, Computing in the Presence of Concurrent Solo Executions. [Bibtex]

Tong-Wook Shinn and Tadao Takaoka, Combining All Pairs Shortest Paths and All Pairs Bottleneck Paths Problems. [Bibtex]

Toshimasa Ishii, Hirotaka Ono and Yushi Uno, (Total) Vector Domination for Graphs with Bounded Branchwidth. [Bibtex]

Martin Farach-Colton and Meng-Tsung Tsai, Computing the Degeneracy of Large Graphs. [Bibtex]

Rolf Klein, Christos Levcopoulos and Andrzej Lingas, Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. [Bibtex]

Sang-Sub Kim and Hee-Kap Ahn, An Improved Data Stream Algorithm for Clustering. [Bibtex]

Ran Duan, Approximation Algorithms for the Gromov Hyperbolicity of Discrete Metric Spaces. [Bibtex]

Stephane Durocher, Omrit Filtser, Robert Fraser, Ali D. Mehrabi and Saeed Mehrabi, A \((7/2)\)-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras. [Bibtex]

Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy and Shubhangi Saraf, Helly-Type Theorems in Property Testing. [Bibtex]

Matthias Englert, Nicolaos Matsakis and Marcin Mucha, New Bounds for Online Packing LPs. [Bibtex]

Binay K. Bhattacharya, Tsunehiko Kameda and Zhao Song, Improved Minmax Regret 1-Center Algorithms for Cactus Networks with c Cycles. [Bibtex]

Jurek Czyzowicz, Dariusz Dereniowski, Leszek Gasieniec, Ralf Klasing, Adrian Kosowski and Dominik Pajak, Collision-Free Network Exploration. [Bibtex]

Peter Allen, Julia Böttcher, Hiệp Hán, Yoshiharu Kohayakawa and Yury Person, Powers of Hamilton Cycles in Pseudorandom Graphs. [Bibtex]

Philippe Duchon and Romaric Duvignau, Local Update Algorithms for Random Graphs. [Bibtex]

Felipe De Campos Mesquita, Letícia Rodrigues Bueno and Rodrigo de Alencar Hausen, Odd Graphs Are Prism-Hamiltonian and Have a Long Cycle. [Bibtex]

Colin McDiarmid and Kerstin Weller, Relatively Bridge-Addable Classes of Graphs. [Bibtex]

Min Chih Lin, Michel J. Mizrahi and Jayme Szwarcfiter, \(O(n)\) Time Algorithms for Dominating Induced Matching Problems. [Bibtex]

Parinya Chalermsook, Bundit Laekhanukit and Danupon Nanongkai, Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation. [Bibtex]

Marie Albenque and Kolja B. Knauer, Convexity in Partial Cubes: The Hull Number. [Bibtex]

Fabrício Benevides, Victor A. Campos, Mitre Costa Dourado, Simon Griffiths, Robert Morris, Leonardo Sampaio and Ana Silva, Connected Greedy Colourings. [Bibtex]

Julien Clément and Laura Giambruno, On the Number of Prefix and Border Tables. [Bibtex]

Elie de Panafieu, Danièle Gardy, Bernhard Gittenberger and Markus Kuba, Probabilities of 2-Xor Functions. [Bibtex]

Antoine Genitrini and Cécile Mailler, Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem. [Bibtex]

Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten Löffler, Joshua Mermelstein, Diane L. Souvaine and Csaba D. Tóth, The Flip Diameter of Rectangulations and Convex Subdivisions. [Bibtex]

Pawel Hitczenko and Svante Janson, Weighted Staircase Tableaux, Asymmetric Exclusion Process, and Eulerian Type Recurrences. [Bibtex]

Nicolas Basset, Counting and Generating Permutations Using Timed Languages. [Bibtex]

Lukas Barth, Sara Irina Fabrikant, Stephen G. Kobourov, Anna Lubiw, Martin Nöllenburg, Yoshio Okamoto, Sergey Pupyrev, Claudio Squarcella, Torsten Ueckerdt and Alexander Wolff, Semantic Word Cloud Representations: Hardness and Approximation Algorithms. [Bibtex]

Florent Foucaud and Reza Naserasr, The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction. [Bibtex]

Pavol Hell and Shenwei Huang, Complexity of Coloring Graphs without Paths and Cycles. [Bibtex]

Nikhil Bansal, Cyriel Rutten, Suzanne van der Ster, Tjark Vredeveld and Ruben van der Zwaan, Approximating Real-Time Scheduling on Identical Machines. [Bibtex]

Lehilton L. C. Pedrosa and Maxim Sviridenko, Integrated Supply Chain Management via Randomized Rounding. [Bibtex]

Mário César San Felice, David P. Williamson and Orlando Lee, The Online Connected Facility Location Problem. [Bibtex]

Amihood Amir, Jessica Ficler, Robert Krauthgamer, Liam Roditty and Oren Sar-Shalom, Multiply Balanced \(k\)-Partitioning. [Bibtex]

Matthias Poloczek, David P. Williamson and Anke van Zuylen, On Some Recent Approximation Algorithms for MAX SAT. [Bibtex]

Antonios Antoniadis, Neal Barcelo, Daniel Cole, Kyle Fox, Benjamin Moseley, Michael Nugent and Kirk Pruhs, Packet Forwarding Algorithms in a Line Network. [Bibtex]

Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis and Eduardo Pacheco, Survivability of Swarms of Bouncing Robots. [Bibtex]

Kévin Perrot and Eric Rémila, Emergence of Wave Patterns on Kadanoff Sandpiles. [Bibtex]

Deepanjan Kesh and Shashank K. Mehta, A Divide and Conquer Method to Compute Binomial Ideals. [Bibtex]

Martin Fürer, How Fast Can We Multiply Large Integers on an Actual Computer. [Bibtex]

Carla Negri Lintzmayer and Zanoni Dias, Sorting Permutations by Prefix and Suffix Versions of Reversals and Transpositions. [Bibtex]

Anna Adamaszek and Alexandru Popa, Algorithmic and Hardness Results for the Colorful Components Problems. [Bibtex]

Josep Díaz, Ioannis Giotis, Lefteris M. Kirousis, Evangelos Markakis and Maria J. Serna, On the Stability of Generalized Second Price Auctions with Budgets. [Bibtex]

Cristina G. Fernandes and Rafael C. S. Schouery, Approximation Algorithms for the Max-Buying Problem with Limited Supply. [Bibtex]

Thibaut Horel, Stratis Ioannidis and S. Muthukrishnan, Budget Feasible Mechanisms for Experimental Design. [Bibtex]

Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Yakov Nekrich and Simon J. Puglisi, LZ77-Based Self-indexing with Faster Pattern Matching. [Bibtex]

Nikolett Bereczky, Amalia Duch, Krisztián Németh and Salvador Roura, Quad-K-d Trees. [Bibtex]

Prosenjit Bose, Rolf Fagerberg, John Howat and Pat Morin, Biased Predecessor Search. [Bibtex]

[Top] [Home] [LATIN 2014]

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 Ruciński, 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. H. 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 Ruciński 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 S. 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 \(\ell_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, Erdős 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 \(\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. H. 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\omega_n\). [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 \(C_k\) Splines on the Sphere. [Bibtex]

Luerbio Faria, Celina M. H. 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]

Celina 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. M. 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 \(\mathcal{M}\)-Subsets of a Free Monoid. [Bibtex]

Alair Pereira do Lago, On the Burnside Semigroups \(x^n = x^{n+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 MOD\(_q\) 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]