Skip to main content
SpringerLink
Log in
Book cover

LATIN 2014: Theoretical Informatics

11th Latin American Symposium, Montevideo, Uruguay, March 31 -- April 4, 2014. Proceedings

  • Conference proceedings
  • © 2014

Overview

Editors:
  1. Alberto Pardo

    1. Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Alfredo Viola

    1. Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 8392)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: LATIN 2014.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (65 papers)

  1. Front Matter

    Download chapter PDF

  2. Complexity 1

    1. Conjugacy in Baumslag’s Group, Generic Case Complexity, and Division in Power Circuits

      • Volker Diekert, Alexei G. Myasnikov, Armin Weiß
      Pages 1-12

    2. Hierarchical Complexity of 2-Clique-Colouring Weakly Chordal Graphs and Perfect Graphs Having Cliques of Size at Least 3

      • Helio B. Macêdo Filho, Raphael C. S. Machado, Celina M. H. Figueiredo
      Pages 13-23

    3. The Computational Complexity of the Game of Set and Its Theoretical Applications

      • Michael Lampis, Valia Mitsou
      Pages 24-34

  3. Complexity 2

    1. Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line

      • José R. Correa, Laurent Feuilloley, José A. Soto
      Pages 35-46

    2. Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds

      • Nikhil Bansal, Tjark Vredeveld, Ruben van der Zwaan
      Pages 47-59

    3. False-Name Manipulation in Weighted Voting Games Is Hard for Probabilistic Polynomial Time

      • Anja Rey, Jörg Rothe
      Pages 60-71

    4. A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width

      • Martin Fürer
      Pages 72-83

  4. Computational Geometry 1

    1. Optimal Algorithms for Constrained 1-Center Problems

      • Luis Barba, Prosenjit Bose, Stefan Langerman
      Pages 84-95

    2. A Randomized Incremental Approach for the Hausdorff Voronoi Diagram of Non-crossing Clusters

      • Panagiotis Cheilaris, Elena Khramtcova, Stefan Langerman, Evanthia Papadopoulou
      Pages 96-107

    3. Upper Bounds on the Spanning Ratio of Constrained Theta-Graphs

      • Prosenjit Bose, André van Renssen
      Pages 108-119

    4. Computing the L 1 Geodesic Diameter and Center of a Simple Polygon in Linear Time

      • Sang Won Bae, Matias Korman, Yoshio Okamoto, Haitao Wang
      Pages 120-131

  5. Graph Drawing

    1. The Planar Slope Number of Subcubic Graphs

      • Emilio Di Giacomo, Giuseppe Liotta, Fabrizio Montecchiani
      Pages 132-143

    2. Smooth Orthogonal Drawings of Planar Graphs

      • Muhammad Jawaherul Alam, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov, Alexander Wolff
      Pages 144-155

    3. Drawing HV-Restricted Planar Graphs

      • Stephane Durocher, Stefan Felsner, Saeed Mehrabi, Debajyoti Mondal
      Pages 156-167

    4. Periodic Planar Straight-Frame Drawings with Polynomial Resolution

      • Luca Castelli Aleardi, Éric Fusy, Anatolii Kostrygin
      Pages 168-179

  6. Automata

    1. A Characterization of Those Automata That Structurally Generate Finite Groups

      • Ines Klimann, Matthieu Picantin
      Pages 180-189

    2. Linear Grammars with One-Sided Contexts and Their Automaton Representation

      • Mikhail Barash, Alexander Okhotin
      Pages 190-201

  7. Computability

    1. On the Computability of Relations on λ-Terms and Rice’s Theorem - The Case of the Expansion Problem for Explicit Substitutions

      • Edward Hermann Haeusler, Mauricio Ayala-Rincón
      Pages 202-213

    2. Computing in the Presence of Concurrent Solo Executions

      • Maurice Herlihy, Sergio Rajsbaum, Michel Raynal, Julien Stainer
      Pages 214-225
Back to top

Other volumes

  1. LATIN 2014: Theoretical Informatics

Keywords

About this book

This book constitutes the refereed proceedings of the 11th Latin American Symposium on Theoretical Informatics, LATIN 2014, held in Montevideo, Uruguay, in March/April 2014. The 65 papers presented together with 5 abstracts were carefully reviewed and selected from 192 submissions. The papers address a variety of topics in theoretical computer science with a certain focus on complexity, computational geometry, graph drawing, automata, computability, algorithms on graphs, algorithms, random structures, complexity on graphs, analytic combinatorics, analytic and enumerative combinatorics, approximation algorithms, analysis of algorithms, computational algebra, applications to bioinformatics, budget problems and algorithms and data structures.

Editors and Affiliations

  • Facultad de Ingeniería, Instituto de Computación, Universidad de la República, Montevideo, Uruguay

    Alberto Pardo, Alfredo Viola

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation