9. LATIN 2010: Oaxaca, Mexico

• Cristopher Moore:
  Continuous and Discrete Methods in Computer Science. 1
  
• Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, Perouz Taslakian:
  Colorful Strips. 2-13
  
• Jonathan Backer, J. Mark Keil:
  The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions. 14-25
  
• Qianping Gu, Navid Imani:
  Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set. 26-37
  
• Eric Angel, Evripidis Bampis, Nicolas Thibault:
  Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machines. 38-48
  
• Martin Fürer:
  Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width. 49-59
  
• Nadja Betzler, Jiong Guo, Christian Komusiewicz, Rolf Niedermeier:
  Average Parameterization and Partial Kernelization for Computing Medians. 60-71
  
• Fedor V. Fomin, Daniel Lokshtanov, Fabrizio Grandoni, Saket Saurabh:
  Sharp Separation and Applications to Exact and Parameterized Algorithms. 72-83
  
• Tsunehiko Kameda, Ichiro Suzuki, John Z. Zhang:
  Finding the Minimum-Distance Schedule for a Boundary Searcher with a Flashlight. 84-95
  
• Salvatore La Torre, Parthasarathy Madhusudan, Gennaro Parlato:
  The Language Theory of Bounded Context-Switching. 96-107
  
• Diego Recalde, Cyriel Rutten, Petra Schuurman, Tjark Vredeveld:
  Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling. 108-119
  
• Britta Peis, Martin Skutella, Andreas Wiese:
  Packet Routing on the Grid. 120-130
  
• Michael D. Coury, Pavol Hell, Jan Kratochvíl, Tomás Vyskocil:
  Faithful Representations of Graphs by Islands in the Extended Grid. 131-142
  
• Gero Greiner, Riko Jacob:
  The I/O Complexity of Sparse Matrix Dense Matrix Multiplication. 143-156
  
• Piotr Indyk:
  Sparse Recovery Using Sparse Random Matrices. 157
  
• Johannes Fischer:
  Optimal Succinctness for Range Minimum Queries. 158-169
  
• Jérémy Barbay, Francisco Claude, Gonzalo Navarro:
  Compact Rich-Functional Binary Relation Representations. 170-183
  
• Sylvain Lombardy, Jacques Sakarovitch:
  Radix Cross-Sections for Length Morphisms. 184-195
  
• Viliam Geffert, Giovanni Pighizzini:
  Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata. 196-207
  
• Janusz A. Brzozowski, Galina Jirásková, Baiyu Li:
  Quotient Complexity of Ideal Languages. 208-221
  
• Frédérique Bassino, Laura Giambruno, Cyril Nicaud:
  Complexity of Operations on Cofinite Languages. 222-233
  
• Hagai Cohen, Ely Porat:
  Fast Set Intersection and Two-Patterns Matching. 234-242
  
• Joachim von zur Gathen, Alfredo Viola, Konstantin Ziegler:
  Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields. 243-254
  
• Beate Bollig:
  A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication. 255-266
  
• Manfred G. Madritsch, Brigitte Vallée:
  Modelling the LLL Algorithm by Sandpiles. 267-281
  
• Prosenjit Bose, Paz Carmi, Michiel H. M. Smid, Daming Xu:
  Communication-Efficient Construction of the Plane Localized Delaunay Graph. 282-293
  
• Dominik Gall, Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig:
  Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization. 294-305
  
• Petra Berenbrink, Robert Elsässer, Thomas Sauerwald:
  Randomised Broadcasting: Memory vs. Randomness. 306-319
  
• Vonjy Rasendrahasina, Vlady Ravelomanana:
  Limit Theorems for Random MAX-2-XORSAT. 320-331
  
• Per Austrin, Siavosh Benabbas, Avner Magen:
  On Quadratic Threshold CSPs. 332-343
  
• Carles Padró, Leonor Vázquez:
  Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming. 344-355
  
• Elizabeth Maltais, Lucia Moura:
  Finding the Best CAFE Is NP-Hard. 356-371
  
• Anna Gál, Jing-Tang Jang:
  The Size and Depth of Layered Boolean Circuits. 372-383
  
• Pankaj K. Agarwal, Jeff M. Phillips, Bardia Sadri:
  Lipschitz Unimodal and Isotonic Regression on Paths and Trees. 384-396
  
• Daniel Panario, Brett Stevens, Qiang Wang:
  Ambiguity and Deficiency in Costas Arrays and APN Permutations. 397-406
  
• Sergio Rajsbaum:
  Iterated Shared Memory Models. 407-416
  
• Emden R. Gansner, Yifan Hu, Michael Kaufmann, Stephen G. Kobourov:
  Optimal Polygonal Representation of Planar Graphs. 417-432
  
• Adrian Dumitrescu, Minghui Jiang:
  Minimum-Perimeter Intersecting Polygons. 433-445
  
• Qi Cheng, Yu-Hsin Li:
  Finding the Smallest Gap between Sums of Square Roots. 446-455
  
• 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, Perouz Taslakian:
  Matching Points with Things. 456-467
  
• Bettina Speckmann, Kevin Verbeek:
  Homotopic Rectilinear Routing with Few Links and Thick Edges. 468-479
  
• Alexis Ballier, Bruno Durand, Emmanuel Jeandel:
  Tilings Robust to Errors. 480-491
  
• Steven Bitner, Yam Ki Cheung, Atlas F. Cook, Ovidiu Daescu, Anastasia Kurdia, Carola Wenk:
  Visiting a Sequence of Points with a Bevel-Tip Needle. 492-502
  
• MohammadHossein Bateni, MohammadTaghi Hajiaghayi:
  Euclidean Prize-Collecting Steiner Forest. 503-514
  
• MohammadTaghi Hajiaghayi, Arefeh A. Nasri:
  Prize-Collecting Steiner Networks via Iterative Rounding. 515-526
  
• René van Bevern, Hannes Moser, Rolf Niedermeier:
  Kernelization through Tidying. 527-538
  
• Mark van Hoeij, Andrew Novocin:
  Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials. 539-553
  
• Christine Chung, Katrina Ligett, Kirk Pruhs, Aaron Roth:
  The Power of Fair Pricing Mechanisms. 554-564
  
• Vahab S. Mirrokni, S. Muthukrishnan, Uri Nadav:
  Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization. 565-576
  
• Leslie G. Valiant:
  Some Observations on Holographic Algorithms. 577-590
  
• Jaroslaw Byrka, Andreas Karrenbauer, Laura Sanità:
  The Interval Constrained 3-Coloring Problem. 591-602
  
• Paul S. Bonsma, Felix Breuer:
  Counting Hexagonal Patches and Independent Sets in Circle Graphs. 603-614
  
• Yuichi Asahiro, Eiji Miyano, Kazuaki Samizo:
  Approximating Maximum Diameter-Bounded Subgraphs. 615-626
  
• Kunal Dutta, C. R. Subramanian:
  Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration. 627-637
  
• Qi Ge, Daniel Stefankovic:
  The Complexity of Counting Eulerian Tours in 4-Regular Graphs. 638-649
  
• Andreas Brandstädt, Christian Hundt, Ragnar Nevries:
  Efficient Edge Domination on Hole-Free Graphs in Polynomial Time. 650-661
  
• Marek Karpinski, Andrzej Rucinski, Edyta Szymanska:
  Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. 662-673
  
• Amalia Duch, Rosa M. Jiménez, Conrado Martínez:
  Rank Selection in Multidimensional Data. 674-685
  
• Prosenjit Bose, Karim Douïeb, Vida Dujmovic, John Howat:
  Layered Working-Set Trees. 686-696
  
• Paolo Ferragina, Travis Gagie, Giovanni Manzini:
  Lightweight Data Indexing and Compression in External Memory. 697-710
  

Last update Fri May 24 12:10:29 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page