@proceedings{DBLP:conf/latin/2006,
  editor    = {Jos{\'e} R. Correa and Alejandro Hevia and Marcos A. Kiwi},
  title     = {LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings},
  booktitle = {LATIN},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {3887},
  year      = {2006},
  isbn      = {3-540-32755-X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@InProceedings{i06-p1-7,
  AUTHOR	= {Ricardo Baeza-Yates},
  TITLE		= {Algorithmic Challenges in Web Search Engines},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {1--7},
  KEYWORDS	= {}}

@InProceedings{i06-p8-10,
  AUTHOR	= {Anne Condon},
  TITLE		= {RNA Molecules: Glimpses Through an Algorithmic Lens},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {8--10},
  KEYWORDS	= {}}

@InProceedings{i06-p11-12,
  AUTHOR	= {Ferran Hurtado},
  TITLE		= {Squares},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {11--12},
  KEYWORDS	= {}}

@InProceedings{i06-p13-24,
  AUTHOR	= {R. Ravi},
  TITLE		= {Matching Based Augmentations for Approximating Connectivity Problems},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {13--24},
  KEYWORDS	= {}}

@InProceedings{i06-p25-25,
  AUTHOR	= {Madhu Sudan},
  TITLE		= {Modelling Errors and Recovery for Communication},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {25--25},
  KEYWORDS	= {}}

@InProceedings{i06-p26-27,
  AUTHOR	= {Sergio Verd\'u},
  TITLE		= {Lossless Data Compression Via Error Correction},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {26--27},
  KEYWORDS	= {}}

@InProceedings{i06-p28-29,
  AUTHOR	= {Avi Wigderson},
  TITLE		= {The Power and Weakness of Randomness in Computation},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {28--29},
  KEYWORDS	= {}}

@InProceedings{l06-p30-42,
  AUTHOR	= {Saurabh Agarwal and Gudmund~Skovbjerg Frandsen},
  TITLE		= {A New GCD Algorithm for Quadratic Number Rings with Unique Factorization},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {30--42},
  KEYWORDS	= {}}

@InProceedings{l06-p43-55,
  AUTHOR	= {Nir Ailon and Steve Chien and Cynthia Dwork},
  TITLE		= {On Clusters in Markov Chains},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {43--55},
  KEYWORDS	= {}}

@InProceedings{l06-p56-67,
  AUTHOR	= {Mikl\'os Ajtai and Cynthia Dwork and Larry~J. Stockmeyer},
  TITLE		= {An Architecture for Provably Secure Computation},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {56--67},
  KEYWORDS	= {}}

@InProceedings{l06-p68-79,
  AUTHOR	= {El\'oi Ara\'ujo and Jos\'e Soares},
  TITLE		= {Scoring Matrices That Induce Metrics on Sequences},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {68--79},
  KEYWORDS	= {}}

@InProceedings{l06-p80-92,
  AUTHOR	= {Boris Aronov and Prosenjit Bose and Erik~D. Demaine and Joachim Gudmundsson and John Iacono and Stefan Langerman and Michiel~H.~M. Smid},
  TITLE		= {Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {80--92},
  KEYWORDS	= {}}

@InProceedings{l06-p93-104,
  AUTHOR	= {Boris Aronov and Alan~R. Davis and John Iacono and Albert~Siu~Cheong Yu},
  TITLE		= {The Complexity of Diffuse Reflections in a Simple Polygon},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {93--104},
  KEYWORDS	= {}}

@InProceedings{l06-p105-117,
  AUTHOR	= {Argimiro Arratia and Carlos Ortiz},
  TITLE		= {Counting Proportions of Sets: Expressive Power with Almost Order},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {105--117},
  KEYWORDS	= {}}

@InProceedings{l06-p118-129,
  AUTHOR	= {Abdullah~N. Arslan},
  TITLE		= {Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {118--129},
  KEYWORDS	= {}}

@InProceedings{l06-p130-141,
  AUTHOR	= {Nuttapong Attrapadung and Yang Cui and David Galindo and Goichiro Hanaoka and Ichiro Hasuo and Hideki Imai and Kanta Matsuura and Peng Yang and Rui Zhang},
  TITLE		= {Relations Among Notions of Security for Identity Based Encryption Schemes},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {130--141},
  KEYWORDS	= {}}

@InProceedings{l06-p142-153,
  AUTHOR	= {Ilya Baran and Erik~D. Demaine and Dmitriy~A. Katz},
  TITLE		= {Optimally Adaptive Integration of Univariate Lipschitz Functions},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {142--153},
  KEYWORDS	= {}}

@InProceedings{l06-p154-165,
  AUTHOR	= {Benjam\'{\i}n~Ren\'e~Callejas Bedregal and Santiago Figueira},
  TITLE		= {Classical Computability and Fuzzy Turing Machines},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {154--165},
  KEYWORDS	= {}}

@InProceedings{l06-p166-177,
  AUTHOR	= {Boaz Ben-Moshe and Binay~K. Bhattacharya and Qiaosheng Shi},
  TITLE		= {An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {166--177},
  KEYWORDS	= {}}

@InProceedings{l06-p178-189,
  AUTHOR	= {Thorsten Bernholt and Thomas Hofmeister},
  TITLE		= {An Algorithm for a Generalized Maximum Subsequence Problem},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {178--189},
  KEYWORDS	= {}}

@InProceedings{l06-p190-201,
  AUTHOR	= {Nayantara Bhatnagar and Dana Randall and Vijay~V. Vazirani and Eric Vigoda},
  TITLE		= {Random Bichromatic Matchings},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {190--201},
  KEYWORDS	= {}}

@InProceedings{l06-p202-210,
  AUTHOR	= {B\'ela Bollob\'as and Guy Kindler and Imre Leader and Ryan O'Donnell},
  TITLE		= {Eliminating Cycles in the Discrete Torus},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {202--210},
  KEYWORDS	= {}}

@InProceedings{l06-p211-223,
  AUTHOR	= {Claudson~F. Bornstein and Eduardo~Sany Laber and Marcelo Mas},
  TITLE		= {On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {211--223},
  KEYWORDS	= {}}

@InProceedings{l06-p224-237,
  AUTHOR	= {J\'er\'emie Bourdon and Brigitte Vall\'ee},
  TITLE		= {Pattern Matching Statistics on Correlated Sources},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {224--237},
  KEYWORDS	= {}}

@InProceedings{l06-p238-249,
  AUTHOR	= {Patricia Bouyer and Nicolas Markey and Pierre-Alain Reynier},
  TITLE		= {Robust Model-Checking of Linear-Time Properties in Timed Automata},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {238--249},
  KEYWORDS	= {}}

@InProceedings{l06-p250-261,
  AUTHOR        = {Hajo Broersma and Matthew Johnson and Dani\"el Paulusma and Iain~A. Stewart},
  TITLE		= {The Computational Complexity of the Parallel Knock-Out Problem},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {250--261},
  KEYWORDS	= {}}

@InProceedings{l06-p262-273,
  AUTHOR	= {Gruia Calinescu and Adrian Dumitrescu and J\'anos Pach},
  TITLE		= {Reconfigurations in Graphs and Grids},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {262--273},
  KEYWORDS	= {}}

@InProceedings{l06-p274-285,
  AUTHOR	= {Laura Chaubard},
  TITLE		= {C-Varieties, Actions and Wreath Product},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {274--285},
  KEYWORDS	= {}}

@InProceedings{l06-p286-297,
  AUTHOR	= {Edgar Ch\'avez and Stefan Dobrev and Evangelos Kranakis and Jaroslav Opatrny and Ladislav Stacho and Jorge Urrutia},
  TITLE		= {Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {286--297},
  KEYWORDS	= {}}

@InProceedings{l06-p298-310,
  AUTHOR	= {Vicky Choi and Navin Goyal},
  TITLE		= {An Efficient Approximation Algorithm for Point Pattern Matching Under Noise},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {298--310},
  KEYWORDS	= {}}

@InProceedings{l06-p311-322,
  AUTHOR	= {Marek Chrobak and Claire Kenyon and John Noga and Neal~E. Young},
  TITLE		= {Oblivious Medians Via Online Bidding},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {311--322},
  KEYWORDS	= {}}

@InProceedings{l06-p323-336,
  AUTHOR	= {Corinna Cortes and Mehryar Mohri and Ashish Rastogi and Michael Riley},
  TITLE		= {Efficient Computation of the Relative Entropy of Probabilistic Automata},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {323--336},
  KEYWORDS	= {}}

@InProceedings{l06-p337-348,
  AUTHOR	= {Ho-Kwok Dai and Hung-Chi Su},
  TITLE		= {A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {337--348},
  KEYWORDS	= {}}

@InProceedings{l06-p349-361,
  AUTHOR	= {Erik~D. Demaine and Friedhelm Meyer~auf~der~Heide and Rasmus Pagh and Mihai Patrascu},
  TITLE		= {De Dictionariis Dynamicis Pauco Spatio Utentibus (lat. On Dynamic Dictionaries Using Little Space)},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {349--361},
  KEYWORDS	= {}}

@InProceedings{l06-p362-373,
  AUTHOR	= {Sandeep Dey and Nicolas Schabanel},
  TITLE		= {Customized Newspaper Broadcast: Data Broadcast with Dependencies},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {362--373},
  KEYWORDS	= {}}

@InProceedings{l06-p374-385,
  AUTHOR	= {Gabriele Di~Stefano and Stefan Krause and Marco~E. L\"ubbecke and Uwe~T. Zimmermann},
  TITLE		= {On Minimum k-Modal Partitions of Permutations},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {374--385},
  KEYWORDS	= {}}

@InProceedings{l06-p386-397,
  AUTHOR	= {Frederic Dorn and Jan~Arne Telle},
  TITLE		= {Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {386--397},
  KEYWORDS	= {}}

@InProceedings{l06-p398-409,
  AUTHOR	= {Douglas~G. Down and George Karakostas},
  TITLE		= {Maximizing Throughput in Queueing Networks with Limited Flexibility},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {398--409},
  KEYWORDS	= {}}

@InProceedings{l06-p410-422,
  AUTHOR	= {Feodor~F. Dragan and Chenyu Yan},
  TITLE		= {Network Flow Spanners},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {410--422},
  KEYWORDS	= {}}

@InProceedings{l06-p423-434,
  AUTHOR	= {Khaled Elbassioni},
  TITLE		= {Finding All Minimal Infrequent Multi-dimensional Intervals},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {423--434},
  KEYWORDS	= {}}

@InProceedings{l06-p435-446,
  AUTHOR	= {Roee Engelberg and Jochen K\"onemann and Stefano Leonardi and Joseph Naor},
  TITLE		= {Cut Problems in Graphs with a Budget Constraint},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {435--446},
  KEYWORDS	= {}}

@InProceedings{l06-p447-454,
  AUTHOR	= {Martin Farach-Colton and Rohan~J. Fernandes and Miguel~A. Mosteiro},
  TITLE		= {Lower Bounds for Clear Transmissions in Radio Networks},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {447--454},
  KEYWORDS	= {}}

@InProceedings{l06-p455-466,
  AUTHOR	= {Nazim Fat\`es and Damien Regnault and Nicolas Schabanel and Eric Thierry},
  TITLE		= {Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {455--466},
  KEYWORDS	= {}}

@InProceedings{l06-p467-478,
  AUTHOR	= {Herv\'e Fournier and Antoine Vigneron},
  TITLE		= {Lower Bounds for Geometric Diameter Problems},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {467--478},
  KEYWORDS	= {}}

@InProceedings{l06-p479-490,
  AUTHOR	= {Pierre Fraigniaud and Nicolas Nisse},
  TITLE		= {Connected Treewidth and Connected Graph Searching},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {479--490},
  KEYWORDS	= {}}

@InProceedings{l06-p491-501,
  AUTHOR	= {Martin F\"urer},
  TITLE		= {A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {491--501},
  KEYWORDS	= {}}

@InProceedings{l06-p502-514,
  AUTHOR	= {Eli Gafni and Sergio Rajsbaum and Michel Raynal and Corentin Travers},
  TITLE		= {The Committee Decision Problem},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {502--514},
  KEYWORDS	= {}}

@InProceedings{l06-p515-523,
  AUTHOR	= {Ling Gai and Guochuan Zhang},
  TITLE		= {Common Deadline Lazy Bureaucrat Scheduling Revisited},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {515--523},
  KEYWORDS	= {}}

@InProceedings{l06-p524-531,
  AUTHOR	= {Joachim Giesen and Eva Schuberth and Milos Stojakovic},
  TITLE		= {Approximate Sorting},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {524--531},
  KEYWORDS	= {}}

@InProceedings{l06-p532-543,
  AUTHOR	= {Michel~X. Goemans and Jan Vondr\'ak},
  TITLE		= {Stochastic Covering and Adaptivity},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {532--543},
  KEYWORDS	= {}}

@InProceedings{l06-p544-555,
  AUTHOR	= {Parikshit Gopalan and Venkatesan Guruswami and Richard~J. Lipton},
  TITLE		= {Algorithms for Modular Counting of Roots of Multivariate Polynomials},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {544--555},
  KEYWORDS	= {}}

@InProceedings{l06-p556-568,
  AUTHOR	= {Venkatesan Guruswami and Valentine Kabanets},
  TITLE		= {Hardness Amplification Via Space-Efficient Direct Products},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {556--568},
  KEYWORDS	= {}}

@InProceedings{l06-p569-579,
  AUTHOR	= {Mikael Hammar and Bengt~J. Nilsson and Mia Persson},
  TITLE		= {The Online Freeze-Tag Problem},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {569--579},
  KEYWORDS	= {}}

@InProceedings{l06-p580-591,
  AUTHOR	= {Herman~J. Haverkort and Laura Toma},
  TITLE		= {I/O-Efficient Algorithms on Near-Planar Graphs},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {580--591},
  KEYWORDS	= {}}

@InProceedings{l06-p592-604,
  AUTHOR	= {Pinar Heggernes and Federico Mancini},
  TITLE		= {Minimal Split Completions of Graphs},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {592--604},
  KEYWORDS	= {}}

@InProceedings{l06-p605-616,
  AUTHOR	= {Regant~Y.~S. Hung and Hing-Fung Ting},
  TITLE		= {Design and Analysis of Online Batching Systems},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {605--616},
  KEYWORDS	= {}}

@InProceedings{l06-p617-628,
  AUTHOR	= {Wojciech Jawor and Marek Chrobak and Christoph D\"urr},
  TITLE		= {Competitive Analysis of Scheduling Algorithms for Aggregated Links},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {617--628},
  KEYWORDS	= {}}

@InProceedings{l06-p629-640,
  AUTHOR	= {James King},
  TITLE		= {A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {629--640},
  KEYWORDS	= {}}

@InProceedings{l06-p641-652,
  AUTHOR	= {Goran Konjevod and Andr\'ea~W. Richa and Donglin Xia},
  TITLE		= {On Sampling in Higher-Dimensional Peer-to-Peer Systems},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {641--652},
  KEYWORDS	= {}}

@InProceedings{l06-p653-664,
  AUTHOR	= {Evangelos Kranakis and Danny Krizanc and Euripides Markou},
  TITLE		= {Mobile Agent Rendezvous in a Synchronous Torus},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {653--664},
  KEYWORDS	= {}}

@InProceedings{l06-p665-676,
  AUTHOR	= {Lap~Chi Lau and Michael Molloy},
  TITLE		= {Randomly Colouring Graphs with Girth Five and Large Maximum Degree},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {665--676},
  KEYWORDS	= {}}

@InProceedings{l06-p677-688,
  AUTHOR	= {Orlando Lee and Aaron Williams},
  TITLE		= {Packing Dicycle Covers in Planar Graphs with No K5-e Minor},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {677--688},
  KEYWORDS	= {}}

@InProceedings{l06-p689-702,
  AUTHOR        = {Lo\"ick Lhote and Brigitte Vall\'ee},
  TITLE		= {Sharp Estimates for the Main Parameters of the Euclid Algorithm},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {689--702},
  KEYWORDS	= {}}

@InProceedings{l06-p703-714,
  AUTHOR	= {Veli M\"akinen and Gonzalo Navarro},
  TITLE		= {Position-Restricted Substring Searching},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {703--714},
  KEYWORDS	= {}}

@InProceedings{l06-p715-726,
  AUTHOR	= {Yan Mayster and Mario~A. Lopez},
  TITLE		= {Rectilinear Approximation of a Set of Points in the Plane},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {715--726},
  KEYWORDS	= {}}

@InProceedings{l06-p727-736,
  AUTHOR	= {Fr\'ed\'eric Mazoit},
  TITLE		= {The Branch-Width of Circular-Arc Graphs},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {727--736},
  KEYWORDS	= {}}

@InProceedings{l06-p737-744,
  AUTHOR	= {Eduardo Moreno and Mart\'{\i}n Matamala},
  TITLE		= {Minimal Eulerian Circuit in a Labeled Digraph},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {737--744},
  KEYWORDS	= {}}

@InProceedings{l06-p745-756,
  AUTHOR	= {Frank Neumann and Marco Laumanns},
  TITLE		= {Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {745--756},
  KEYWORDS	= {}}

@InProceedings{l06-p757-768,
  AUTHOR	= {Nadia Pisanti and Alexandra~M. Carvalho and Laurent Marsan and Marie-France Sagot},
  TITLE		= {RISOTTO: Fast Extraction of Motifs with Mismatches},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {757--768},
  KEYWORDS	= {}}

@InProceedings{l06-p769-780,
  AUTHOR	= {Mariko Sakashita and Kazuhisa Makino and Satoru Fujishige},
  TITLE		= {Minimum Cost Source Location Problems with Flow Requirements},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {769--780},
  KEYWORDS	= {}}

@InProceedings{l06-p781-792,
  AUTHOR	= {Daniel Sawitzki},
  TITLE		= {Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {781--792},
  KEYWORDS	= {}}

@InProceedings{l06-p793-799,
  AUTHOR	= {Igor Shparlinski and Arne Winterhof},
  TITLE		= {Constructions of Approximately Mutually Unbiased Bases},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {793--799},
  KEYWORDS	= {}}

@InProceedings{l06-p800-811,
  AUTHOR	= {Yngve Villanger},
  TITLE		= {Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In},
  YEAR		= 2006,
  BOOKTITLE	= {Proc.~of the 7th Latin American Symposium on Theoretical Informatics (LATIN'06)},
  ADDRESS	= {Valdivia, Chile},
  PAGES		= {800--811},
  KEYWORDS	= {}}