Accepted papers

LATIN16 Accepted Papers


Andreas Wiese. Independent set of convex polygons: from n^eps to 1+eps via shrinking
Patrick Dragon, Oscar Hernandez and Aaron Williams. The Grandmama de Bruijn Sequence.
Matthias Mnich, Heiko Röglin and Clemens Rösner. New Deterministic Algorithms for Solving Parity Games
Sang Won Bae, Chan-Su Shin and Antoine Vigneron. Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons.
Marek Chrobak and Kevin Costello. Faster Information Gathering in Ad-Hoc Radio Tree Networks
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior and Michele Scquizzato. Chasing Convex Bodies and Functions
Maxime Crochemore, Gabriele Fici, Robert Mercas and Solon Pissis. Linear-Time Sequence Comparison Using Minimal Absent Words
Pål Grønås Drange, Markus Dregi and R.B. Sandeep. Compressing bounded degree graphs
Michal Kotrbcik, Rastislav Kralovic and Sebastian Ordyniak. Edge-editing to a Dense and a Sparse Graph Class
Prosenjit Bose, Michiel Smid and Hill Darryl. Improved Spanning Ratio for Low Degree Spanners.
Carsten Fischer and Heiko Röglin. Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
Edouard Bonnet, Bruno Escoffier, Vangelis Paschos and Georgios Stamoulis. A 0.821-ratio purely combinatorial algorithm for maximum $k$-vertex cover in bipartite graphs
Amalia Duch, Gustavo Lau and Conrado Martínez. Random Partial Match Queries in Quad-$K$-d Trees
Hee-Kap Ahn, Helmut Alt, Maike Buchin, Eunjin Oh, Ludmila Scharf and Carola Wenk. A Middle Curve Based on Discrete Fréchet Distance
Victor Marsault and Jacques Sakarovitch. Trees and Languages with Periodic Signature.
Kolja Knauer and Bartosz Walczak. Graph drawings with one bend and few slopes
Alessio Conte, Roberto Grossi, Andrea Marino and Romeo Rizzi. Listing Acyclic Orientations of Graphs with Single and Multiple Sources
David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides and Steve Wismath. On the Planar Split Thickness of Graphs
Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers. Non-deterministic fault-tolerant distributed decision
Martin Fink, John Hershberger, Subhash Suri and Kevin Verbeek. Bundled Crossings in Embedded Graphs
David Eppstein and Daniel S. Hirschberg. From Discrepancy to Majority
Fernando Benavides and Sergio Rajsbaum. The read/write protocol complex is collapsible
Nirman Kumar and Subhash Suri. Containment and Evasion in Stochastic Point Data
Indranil Banerjee and Dana Richards. Computing Maximal Layers Of Points in $E^{f(n)}$
Samuele Giraudo and Stéphane Vialette. Unshuffling Permutations
Olivier Bodini, Xavier Fontaine, Matthieu Dien, Antoine Genitrini and Hsien-Kuei Hwang. Increasing Diamonds
Merce Claverol, Elena Khramtcova, Evanthia Papadopoulou, Maria Saumell and Carlos Seara. Stabbing circles for sets of segments in the plane
Eunjin Oh, Sang Won Bae and Hee-Kap Ahn. Computing a Geodesic Two-Center of Points in a Simple Polygon
Alice Paul, Matthias Poloczek and David Williamson. Simple Approximation Algorithms for Balanced MAX 2SAT
Evangelos Bampas and David Ilcinkas. On mobile agent verifiable problems
Hossein Esfandiari and Guy Kortsarz. A Bounded-Risk Mechanism for the Kidney Exchange Game
Michael Bender, Rezaul Chowdhury, Alex Conway, Martin Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon and Shikha Singh. The I/O Complexity of Computing Prime Tables
Markus Lohrey, Moses Ganardi, Danny Hucke and Eric Noeth. Tree compression using string grammars
Manfred Cochefert, Jean-Francois Couturier, Serge Gaspers and Dieter Kratsch. Faster algorithms to enumerate hypergraph transversals
Saket Saurabh and Meirav Zehavi. $(k,n-k)$-Max-Cut: An $\OO^*(2^p)$-Time Algorithm and a Polynomial Kernel
Nicholas Harvey and Keyulu Xu. Generating Random Spanning Trees via Fast Matrix Multiplication
Djamal Belazzougui, Travis Gagie, Veli Mäkinen, Marco Previtali and Simon Puglisi. Bidirectional BWT-Based De Bruijn Graphs
Haim Kaplan, Wolfgang Mulzer, Liam Roditty and Paul Seiferth. Routing in Unit Disk Graphs
Amihood Amir, Mika Amit, Gad M. Landau and Dina Sokol. Period Recovery over the Hamming and Edit Distances
Katerina Bohmova, Yann Disser, Matúš Mihalák and Rastislav Sramek. Scheduling Transfers of Resources over Time: Towards Car-Sharing with Flexible Drop-Offs
Michael Bekos, Michael Kaufmann and Robert Krug. On the Total Number of Bends for Planar Octilinear Drawings
Akanksha Agrawal, Daniel Lokshtanov, Sudeshna Kolay and Saket Saurabh. A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion
Kamal Al-Bawani, Matthias Englert and Matthias Westermann. Comparison-based FIFO Buffer Management in QoS Switches
Cristina Fernandes, Samuel P. De Paula and Lehilton L. C. Pedrosa. Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center
Martin Farach-Colton and Meng-Tsung Tsai. Tight Approximations of Graph Degeneracy in Large Graphs
Iffat Chowdhury and Matt Gibson. Constructing Consistent Digital Line Segments
Johannes Fischer, Tomohiro I and Dominik Köppl. Deterministic Sparse Suffix Sorting on Rewritable Texts
Pradeesha Ashok, Sudeshna Kolay and Saket Saurabh. Parameterized Complexity of Red Blue Set Cover for lines
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
Syed Mohammad Meesum and Saket Saurabh. Rank Reduction of Directed Graphs by Vertex and Edge Deletions
Ashutosh Rai, Ramanujan M. S. and Saket Saurabh. A Parameterized Algorithm for Mixed-Cut
Susanne Albers, Evripidis Bampis, Dimitrios Letsios, Giorgio Lucarelli and Richard Stotz. Scheduling on Power-Heterogeneous Processors