LATIN 2008


Chair
Program Committee
Organizing Committee
Invited Speakers
Proceeding
Papers
Sponsors
Location
Photos
Statistics


Chair
Eduardo Laber, PUC-Rio, Brazil.

[Top] [Home] [All LATIN Chairs]

Program Committee
Michael Bender, Stony Brook U., USA.
Leo Bertossi, Carleton U., Canada.
Claudson Bornstein (Vice-chair), U. F. Rio de Janeiro, Brazil.
Ferdinando Cicalese, U. of Salermo, Italy.
José Correa, U. Adolfo Ibáñez , Chile.
Cristina G. Fernandes, U. de São Paulo, Brazil.
David Fernández-Baca, Iowa State U., USA.
Fedor Fomin, U. Bergen, Norway.
Joachim von zur Gathen, U. of Bonn, Germany.
Andrew Goldberg, Microsoft Research Silicon Valley, USA.
Venkatesan Guruswami, U. of Washington, USA.
Alejandro Hevia, U. Chile, Chile.
John Iacono, Polytechnic U., USA.
Eduardo Laber (Chair), PUC-Rio, Brazil.
Alejandro López-Ortiz, U. of Waterloo, Canada.
Arnaldo Mandel, U. de São Paulo, Brazil.
Guilhermo Matera, U. Nacional de General Sarmiento, Argentina.
Flávio Miyazawa, Unicamp, Brasil.
Mike Molloy, U. of Toronto, Canada.
Ojas Parekh, Emory U., USA.
Boaz Patt-Shamir, Tel Aviv U., Israel.
Artur Pessoa, U. F. Fluminense, Brazil.
Jean-Éric Pin, U. of Paris 7, France.
Satish Rao, U. of Berkeley, USA.
R. Ravi, Carnegie Mellon U., USA.
Andrea Richa, Arizona State U., USA.
Miklós Ruszinkó, Computer and Automation Research Institute, Hungary.
Gelasio Salazar, U. Autónoma de San Luis Potosi, Mexico.
Jayme L. Szwarcfiter, U. F. Rio de Janeiro, Brasil.
Tamir Tassa, The Open U., Israel.
Jorge Urrutia, U. Nacional Autónoma de Mexico, Mexico.
Ugo Vaccaro, U. of Salerno, Italy.
Vijay Vazirani, Georgia Tech, USA.
Alfredo Viola, U. de la República, Uruguay.
Renato Werneck, Microsoft Research Silicon Valley, USA.
Frances Yao, City U. of Hong Kong, Hong-Kong.

[Top] [Home] [All LATIN PCs]

Organizing Committee
Claudson Bornstein, Federal University of Rio de Janeiro, Brazil.
Luerbio Faria, State University of Rio de Janeiro, Brazil.
Loana T. Nogueira, Fluminense Federal University, Brazil.

[Top] [Home] [All LATIN Org. Committees]

Invited Speakers
Claudio Lucchesi, (Unicamp, Brazil), Pfaffian Bipartite Graphs: The Elusive Heawood Graph.
Moni Naor, (Weizmann Institute, Israel), Games, Exchanging Information and Extracting Randomness.
Wojciech Szpankowski, (Purdue University, USA), Tries.
Eva Tardos, (Cornell U., USA), Games in Networks.
Robert Tarjan, (Princeton U., USA), Graph Algorithms.

[Top] [Home] [All LATIN Inv. Speakers]

Papers
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] [All LATIN Papers]

Sponsors
CNPq: Conselho Nacional de Desenvolvimento Científico
e Tecnológico CAPES: Coordenação de Aperfeiçoamento de
Pessoal de Nível Superior FAPERJ: Fundação Carlos Chagas Filho de Amparo
à Pesquisa do Estado do Rio de Janeiro UOL
Microsoft Research
IFIP: International Federation for Information Processing
Yahoo! Research
HP Labs

[Top] [Home] [All LATIN Sponsors]

Location

Conference Site

LATIN 2008 took place in Búzios, at the Hotel Atlantico Búzios. The hotel is set in front of a beautiful bay called Armação dos Búzios.

Located in a peninsula 180km Northeast of Rio de Janeiro, Búzios is a charming old fisherman city. Today Búzios is an international touristic spot. The beauty of the 26 surrounding beaches, the typical and international restaurants, the famous boutiques, the shows, its daring architecture with old clay roof tiles and rustic wood, its famous Rua das Pedras, the sea with its Olympic wind where Brazilian champions practice, its arid nature, reminiscent of the Atlantic Forest... Everything makes of Búzios a special place.


[Top] [Home] [All LATIN Locations]

Photos

[Top] [Home] [All LATIN Photos]

Statistics
General:
No. of submissions 242
No. of accepted papers 67
% of accepted papers 27.7%
Total No. of authors 174
Avg. No. of authors per paper 2.60
No. of countries represented 29
 
No. of papers according to how many authors work in Latin-America
    At least one 6(9.0%)
    All 2(3.0%)


Statistics by Country of Author's Affiliation

Authors*Papers**

54.5(31.3%)23.77(35.5%)USA
29.5(17.0%)8.35(12.5%)Canada
14.5(8.3%)5.25(7.8%)France
12.5(7.2%)6.17(9.2%)Germany
6.0(3.4%)1.47(2.2%)Belgium
6.0(3.4%)1.47(2.2%)Norway
6.0(3.4%)1.33(2.0%)Brazil
5.0(2.9%)2.20(3.3%)Israel
4.5(2.6%)1.71(2.5%)Chile
3.0(1.7%)2.00(3.0%)Australia
3.0(1.7%)1.50(2.2%)Netherlands
3.0(1.7%)1.50(2.2%)Japan
3.0(1.7%)0.87(1.3%)Czech Republic
2.0(1.1%)1.00(1.5%)Sweden
2.0(1.1%)1.00(1.5%)Hong Kong
2.0(1.1%)0.29(0.4%)Mexico
2.0(1.1%)0.88(1.3%)Poland
2.0(1.1%)1.33(2.0%)Russia
2.0(1.1%)0.67(1.0%)Finland
2.0(1.1%)0.67(1.0%)Portugal
1.5(0.9%)0.67(1.0%)UK
1.5(0.9%)0.50(0.7%)Hungary
1.0(0.6%)0.25(0.4%)Taiwan
1.0(0.6%)1.00(1.5%)Switzerland
1.0(0.6%)0.20(0.3%)China
1.0(0.6%)0.14(0.2%)Slovakia
1.0(0.6%)0.33(0.5%)Singapore
1.0(0.6%)0.25(0.4%)Spain
0.5(0.3%)0.25(0.4%)Greece

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


Statistics by Region of Author's Affiliation

Authors*Papers**

84.0(48.3%)32.1(47.9%)USA & Canada
61.5(35.3%)24.1(35.9%)Europe
12.5(7.2%)3.3(5.0%)Latin-America
10.0(5.7%)5.1(7.6%)Australia & Asia
5.0(2.9%)2.2(3.3%)Middle East
1.0(0.6%)0.2(0.3%)China

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


Africa

Australia & Asia

Taiwan Hwang, Hsien-Kuei;
Australia Hong, Seok-Hee; Shparlinski, Igor;
Hong Kong Hung, Regant Y. S.; Ting, Hing-Fung;
Japan Inui, Yoshifumi; Le Gall, François; Nagamochi, Hiroshi;
Singapore Santha, Miklos;

China

China Wang, Wencheng;

Europe

UK Bárány, Imre; Erlebach, Thomas;
Sweden Lingas, Andrzej; Lundell, Eva-Marta;
Germany Angelopoulos, Spyros; Bonsma, Paul S.; Brandstädt, Andreas; Hüffner, Falk; Hoefer, Martin; Hundt, Christian; Komusiewicz, Christian; Moser, Hannes; Nekrich, Yakov; Niedermeier, Rolf; Zickfeld, Florian; van Stee, Rob; von zur Gathen, Joachim;
Hungary Bárány, Imre; Ivanyos, Gábor;
Belgium Aloupis, Greg; Blondel, Vincent D.; Cardinal, Jean; Collette, Sébastien; Jungers, Raphael M.; Langerman, Stefan;
Switzerland Scheder, Dominik;
Norway Fomin, Fedor V.; Heggernes, Pinar; Lokshtanov, Daniel; Mancini, Federico; Meister, Daniel; Telle, Jan Arne;
Netherlands Silveira, Rodrigo I.; van Kreveld, Marc J.; van Leeuwen, Erik Jan;
France Abouelaoualim, A.; Akhavi, Ali; Bui-Xuan, Binh-Minh; Das, Kinkar Chandra; Daudé, Hervé; Habib, Michel; Kratsch, Dieter; Manoussakis, Yannis; Nicodème, Pierre; Raspaud, André; Ravelomanana, Vlady; Reed, Bruce; Sanselme, Luc; Stehlé, Damien; Todinca, Ioan;
Slovakia Dobrev, Stefan;
Poland Bienkowski, Marcin; Madry, Aleksander; Suchan, Karol;
Russia Afonin, Sergey; Protasov, Vladimir;
Finland Karhumäki, Juhani; Okhotin, Alexander;
Portugal Oliveira, Arlindo L.; Russo, Luís M. S.;
Spain Martínez, Conrado;
Czech Republic Kratochvíl, Jan; Pór, Attila; Valtr, Pavel;
Greece Markou, Euripides;

Latin-America

Mexico González-Aguilar, H.; Urrutia, Jorge;
Chile González, Rodrigo; Navarro, Gonzalo; Rapaport, Ivan; Suchan, Karol;
Brazil Faria, L.; Fernandes, Cristina G.; Ferreira, Carlos; Martinhon, Carlos; Tjandraatmadja, Christian; Wakabayashi, Yoshiko;

Middle East

Israel Epstein, Leah; Nutov, Zeev; Smorodinsky, Shakhar; Tsanko, Elena;

USA & Canada

Canada Angelopoulos, Spyros; Bose, Prosenjit; Carmi, Paz; Couture, Mathieu; Czyzowicz, Jurek; Dorrigiv, Reza; Fevens, Thomas; Gupta, Arvind; Hell, Pavol; Karakostas, George; Karimi, Mehdi; Kranakis, Evangelos; López-Ortiz, Alejandro; Li, Zhentao; Maheshwari, Anil; Markou, Euripides; Morin, Pat; Moura, Lucia; Opatrny, Jaroslav; Panario, Daniel; Rafiey, Arash; Reed, Bruce; Saad, Rachid; Smid, Michiel H. M.; Stacho, Juraj; Stevens, Brett; Yang, Boting;
USA Angelov, Stanislav; Awerbuch, Baruch; Azimian, Kooshiar; Bansal, Nikhil; Bereg, Sergey; Bern, Marshall W.; Bunde, David P.; Chan, Ho-Leung; Cheng, Christine; Chung, Christine; Cornuéjols, Gérard; Dean, Brian C.; Dellamonica Jr., Domingos; Deshpande, Amol; Dong, Jianrong; Dragan, Feodor F.; Dudek, Andrzej; Fürer, Martin; Fernández-Baca, David; Griffis, Adam; Gupta, Anupam; Hayes, Barry; Hazan, Elad; Ibarra, Oscar H.; Jiang, Minghui; Khandekar, Rohit; Khuller, Samir; Kortsarz, Guy; Krizanc, Danny; Kunal, Keshav; Lopez, Mario; Madry, Aleksander; Malekian, Azarakhsh; Maletti, Andreas; Margot, François; Mayster, Yan; McCutchen, Richard; McGregor, Andrew; Mirrokni, Vahab S.; Panigrahy, Rina; Park, GaHyun; Pruhs, Kirk; Rödl, Vojtech; Szegedy, Mario; Szpankowski, Wojciech; Talwar, Kunal; Toossi, Mohammed; Uthaisombut, Patchrawat; Verstraëte, Jacques; Whitley, Adam; Xiang, Yang; Yan, Chenyu; Zhu, Binhai;


[Top] [Home] [All LATIN Statistics]