LATIN 2012 Accepted Papers

Zeev Nutov Survivable Network Activation Problems
Zeev Nutov Degree-Constrained Node-Connectivity
Tinaz Ekim, Aysel Erey, Pinar Heggernes, Pim Van 'T Hof and Daniel Meister Computing minimum geodetic sets in proper interval graphs
Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela and Jorma Tarhio Indexed Multi-Pattern Matching
Pierre Fraigniaud and Andrzej Pelc Decidability Classes for Mobile Agents Computing
Armando Castaneda, Damien Imbs, Sergio Rajsbaum and Michel Raynal Renaming is Weaker than Set Agreement but for Perfect Renaming: A Map of Sub-Consensus Tasks
Monaldo Mastrolilli The Feedback Arc Set Problem with Triangle Inequality is a Vertex Cover Problem
Armando Castaneda, Maurice Herlihy and Sergio Rajsbaum An Equivariance Theorem with Applications to Renaming
Amir Shpilka Capacity achieving two-write WOM codes
Bernard Mans and Igor Shparlinski Random Walks and Bisections in Random Circulant Graphs
Jiawei Qian, Frans Schalekamp, David Williamson and Anke Van Zuylen On the Integrality Gap of the Subtour LP for the 1,2-TSP
Zoltan Esik and Szabolcs Ivan Context-free ordinals
Eda Cesaratto and Brigitte Vallée Pseudo-randomness of a random Kronecker sequence
Volker Diekert, Jonathan Kausch and Markus Lohrey Logspace computations in graph groups and Coxeter groups
Linqing Tang and Peng Zhang Approximating Minimum Label $s$-$t$ Cut via Linear Programming
Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Venkatesh Raman Parameterized Complexity of MaxSat Above Average
Martin Kutrib, Andreas Malcher and Giovanni Pighizzini Oblivious Two-Way Finite Automata: Decidability and Complexity
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk Solving the 2-Disjoint Connected Subgraphs problem faster than 2^n
Martin Farach-Colton, Antonio Fernandez Anta, Alessia Milani, Miguel A. Mosteiro and Shmuel Zaks Opportunistic Information Dissemination in Mobile Ad-hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism
Hélio B. Macêdo Filho, Raphael Machado and Celina Figueiredo Clique-colouring and biclique-colouring unichord-free graphs
Richard Cole and Vijaya Ramachandran Revisiting the Cache Miss Analysis of Multithreaded Algorithms
Hadas Shachnai, Gal Tamir and Tami Tamir A Theory and Algorithms for Combinatorial Reoptimization
Mitre C. Dourado, Dieter Rautenbach, Vinicius Fernandes Dos Santos, Philipp M. Schaefer, Jayme L. Szwarcfiter and Alexandre Toman On the Radon Number for $P_3$-Convexity
Michel Habib, Antoine Mamcarz and Fabien De Montgolfier Algorithms for some H -join decompositions.
Krzysztof Fleszar, Christian Glasser, Fabian Lipp, Christian Reitwießner and Maximilian Witek Structural Complexity of Multiobjective NP Search Problems
Gero Greiner and Riko Jacob The Efficiency of MapReduce in Parallel External Memory
Prosenjit Bose, Rolf Fagerberg, André Van Renssen and Sander Verdonschot On Plane Constrained Bounded-Degree Spanners
Mohammadamin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Vahab Mirrokni and Sina Sadeghian Sadeghabad On the Non-progressive Spread of Influence through Social Networks
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
Jean Cardinal and Matias Korman Coloring Planar Homothets and Three-Dimensional Hypergraphs
Bin Fu NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets
Hee-Kap Ahn, Samg Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama and Antoine Vigneron A Generalization of the Convex Kakeya Problem
Hans-Joachim Boeckenhauer, Dennis Komm, Richard Kralovic and Peter Rossmanith On the Advice Complexity of the Knapsack Problem
Nicolas Boria, Jerome Monnot and Vangelis Paschos Reoptimization of maximum induced hereditary subgraph problem
Vikraman Arvind, Partha Mukhopadhyay and Prajakta Nimbhorkar Erd\H{o}s-R\'{e}nyi Sequences and Deterministic construction of Expanding Cayley Graphs
Xiaoming Sun, Chengu Wang and Wei Yu The Relationship between Inner Product and Counting Cycles
Wiebke Höhn and Tobias Jacobs On the performance of Smith's rule in single-machine scheduling with nonlinear cost
Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela and Niko Välimäki Forbidden Patterns
Rohit Khandekar, Guy Kortsarz and Vahab Mirrokni On the advantage of overlapping clusters for minimizing conductance
Archontia Giannopoulou, Sudeshna Kolay and Saket Saurabh New Lower Bound on Max-Cut of hypergraphs with an application to {\sc $r$-Set Splitting}
Daniel Heldt, Kolja Knauer and Torsten Ueckerdt On the bend-number of planar and outerplanar graphs
Toryn Qwyllyn Klassen and Philipp Woelfel Independence of Tabulation-Based Hash Classes
Basile Morcrette Fully Analyzing an Algebraic Polya Urn Model
Esther Arkin, José-Miguel Díaz-Báñez, Ferran Hurtado, Piyush Kumar, Joseph Mitchell, Belen Palop, Pablo Pérez-Lantero, Maria Saumell and Rodrigo Silveira Bichromatic 2-center of pairs of points
Ana Busic, Nazim Fates, Jean Mairesse and Irene Marcovici Density classification on infinite lattices and trees
Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman and Ravi Sundaram Cache me if you can: Capacitated Selfish Replication Games
Daniel Dadush A O(1/eps^2)^n Sieving Algorithm for Approximate Integer Programming
Domingos Dellamonica Jr, Yoshiharu Kohayakawa, Vojtech Rödl and Andrzej Rucinski An improved upper bound on the density of universal random graphs
Rafael Barbosa and Yoshiko Wakabayashi A better approximation ratio and an IP formulation for a sensor cover problem
Ahmed Helmi, Conrado Martinez and Alois Panholzer Hiring above the m-th best candidate: a generalization of records in permutations
Joshua Brody, Hongyu Liang and Xiaoming Sun Space-Efficient Approximation Scheme for Circular Earth Mover Distance
Martin Fürer Efficient arbitrary and resolution proofs of unsatisfiability for restricted tree-width
Fedor Fomin, Serge Gaspers, Petr Golovach, Karol Suchan, Stefan Szeider, Erik Jan Van Leeuwen, Martin Vatshelle and Yngve Villanger k-Gap Interval Graphs
Eric Angel, Evripidis Bampis and Vincent Chau Low complexity scheduling algorithm minimizing the energy for tasks with agreeable deadlines
Pooya Davoodi, Michiel Smid and Freek Van Walderveen Two-Dimensional Range Diameter