Skip to main content
SpringerLink
Log in
Book cover

LATIN 2020: Theoretical Informatics

14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings

  • Conference proceedings
  • © 2020

Overview

Editors:
  1. Yoshiharu Kohayakawa

    1. University of São Paulo, São Paulo, Brazil

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Flávio Keidi Miyazawa

    1. University of Campinas, Campinas, Brazil

    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 12118)

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

Included in the following conference series:

Conference proceedings info: LATIN 2021.

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 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.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 (50 papers)

  1. Front Matter

    Pages i-xix
    Download chapter PDF

  2. Approximation Algorithms

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. PTAS for Steiner Tree on Map Graphs

      • Jarosław Byrka, Mateusz Lewandowski, Syed Mohammad Meesum, Joachim Spoerhase, Sumedha Uniyal
      Pages 3-14

    3. Near-Linear Time Algorithm for Approximate Minimum Degree Spanning Trees

      • Ran Duan, Haoqing He, Tianyi Zhang
      Pages 15-26

    4. Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations

      • Khaled Elbassioni
      Pages 27-37

    5. Scheduling on Hybrid Platforms: Improved Approximability Window

      • Vincent Fagnon, Imed Kacem, Giorgio Lucarelli, Bertrand Simon
      Pages 38-49

    6. Leafy Spanning Arborescences in DAGs

      • Cristina G. Fernandes, Carla N. Lintzmayer
      Pages 50-62

    7. Approximating Routing and Connectivity Problems with Multiple Distances

      • Lehilton L. C. Pedrosa, Greis Y. O. Quesquén
      Pages 63-75

    8. A 2-Approximation for the k-Prize-Collecting Steiner Tree Problem

      • Lehilton L. C. Pedrosa, Hugo K. K. Rosado
      Pages 76-88

  3. Parameterized Algorithms

    1. Front Matter

      Pages 89-89
      Download chapter PDF

    2. Maximizing Happiness in Graphs of Bounded Clique-Width

      • Ivan Bliznets, Danil Sagunov
      Pages 91-103

    3. Graph Hamiltonicity Parameterized by Proper Interval Deletion Set

      • Petr A. Golovach, R. Krithika, Abhishek Sahu, Saket Saurabh, Meirav Zehavi
      Pages 104-115

    4. Graph Square Roots of Small Distance from Degree One Graphs

      • Petr A. Golovach, Paloma T. Lima, Charis Papadopoulos
      Pages 116-128

    5. Structural Parameterizations for Equitable Coloring

      • Guilherme C. M. Gomes, Matheus R. Guedes, Vinicius F. dos Santos
      Pages 129-140

  4. Algorithms and Data Structures

    1. Front Matter

      Pages 141-141
      Download chapter PDF

    2. Dynamically Optimal Self-adjusting Single-Source Tree Networks

      • Chen Avin, Kaushik Mondal, Stefan Schmid
      Pages 143-154

    3. Batched Predecessor and Sorting with Size-Priced Information in External Memory

      • Michael A. Bender, Mayank Goswami, Dzejla Medjedovic, Pablo Montes, Kostas Tsichlas
      Pages 155-167

    4. Probabilistically Faulty Searching on a Half-Line

      • Anthony Bonato, Konstantinos Georgiou, Calum MacRury, Paweł Prałat
      Pages 168-180

    5. Query Minimization Under Stochastic Uncertainty

      • Steven Chaplick, Magnús M. Halldórsson, Murilo S. de Lima, Tigran Tonoyan
      Pages 181-193

    6. Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries

      • Shunsuke Inenaga
      Pages 194-206
Back to top

Other volumes

  1. LATIN 2020: Theoretical Informatics

Keywords

About this book

This book constitutes the refereed proceedings of the 14th Latin American Symposium on Theoretical Informatics, LATIN 2020, held in  Sao Paulo, Brazil, in January 2021.

The 50 full papers presented in this book were carefully reviewed and selected from 136 submissions. The papers are grouped into these topics: approximation algorithms; parameterized algorithms; algorithms and data structures; computational geometry; complexity theory; quantum computing; neural networks and biologically inspired computing; randomization; combinatorics; analytic and enumerative combinatorics; graph theory.

Due to the Corona pandemic the event was postponed from May 2020 to January 2021.


Editors and Affiliations

  • University of São Paulo, São Paulo, Brazil

    Yoshiharu Kohayakawa

  • University of Campinas, Campinas, Brazil

    Flávio Keidi Miyazawa

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation