XI Latin and American Algorithms, Graphs and Optimization Symposium

May 17-21, 2021. ONLINE Conference.
Originally scheduled to be in SĂŁo Paulo, Brazil.

LAGOS 2021

(Please, always check the News! section.)


LAGOS 2021 will be held on May 17-21 2021, a virtual conference, originally scheduled to be in SĂŁo Paulo, Brazil. The previous editions were held in Fortaleza, Brazil (GRACO 2001), Santiago, Chile (LACGA 2004), Angra dos Reis, Brazil (GRACO 2005), Puerto Varas, Chile (LAGOS 2007), Gramado, Brazil (LAGOS 2009), Bariloche, Argentina (LAGOS 2011), Playa del Carmen, Mexico (LAGOS 2013), Fortaleza, Brazil (LAGOS 2015), Marseille, France (LAGOS 2017), and Belo Horizonte, Brazil (LAGOS 2019). More information on the history of LAGOS can be found in the memory page.

This year's edition will be very special because we will celebrate the 70th birthday of our beloved Yoshiko Wakabayashi.

Scope and topics

Conference themes include, but are not limited to, the following AMS classifications:

  • Algorithms and complexity: algorithms and computational complexity; approximation algorithms; randomized algorithms; computational geometry; parameterized complexity.
  • Operations Research and Mathematical Programming: combinatorial optimization; integer programming; polyhedral combinatorics; operations research and management science.
  • Graph Theory: cliques, dominating and independent sets; colorings; covering and packing, factorization, matching; digraphs, tournaments; graph algorithms; graphs and matrices; hypergraphs; perfect graphs; random graphs; structural characterization of graph classes.
  • Applications to real-world problems: mathematical programming, combinatorial optimization, continuous optimization, heuristics, and metaheuristics.


🆕 Fev 1, 2022

The proceedings of LAGOS 2021 are now available.

Jan 3, 2022

The deadline for submitting to the special issue is now January 31, 2022.

The call for papers can be found here.

Jun 29, 2021

LAGOS 2021 was a great success, thanks to all the participants!

Photos of the event are available, and the videos will be available soon.
Please contact us if you need a certificate or any other kind of document.

Details of the awardees are also available!

Jun 2, 2021

Following the tradition of LAGOS, a special issue of Discrete Applied Mathematics will be dedicated to LAGOS 2021.

All interested researchers are invited to contribute to this special issue, including those not presented at the symposium.

The call for papers can be found here.

May 20, 2021

Due to some technical issues, the talk for the paper "Tridiagonal Maximum-Entropy Sampling and Tridiagonal Masks", by Hessa Al Thani and Jon Lee will happen at 10:40 on Friday, in Session 18.

May 19, 2021

The special session for Yoshiko Wakabayashi, which will happen on Friday at 3:15 PM will be transmitted live on YouTube!.

May 17, 2021

Some of you may have experienced some issues to access the Virtual Chair System around 2 PM (BRT Time).
There was a momentary outage on Gather's end, but this problem was already resolved.
If something like this happens again, we ask you to clear the cache of your browser and then try and log in again.
Also, please send us an e-mail to let us know, with a copy to help+lagos-2021@virtualchair.net.

May 16, 2021

We ask all the participants to check their email account (the one used in the ECOS system), since there are important messages we've sent you.
The first one is the details on how to access the Virtual Chair system.
The second one is a preview of the proceedings.
Speakers and chairs have also received some specific instructions.

We look forward to seeing you all tomorrow!

May 16, 2021

The LAGOS 2021 proceedings were previously planned to be published in the Electronic Notes on Theoretical Computer Science (ENTCS), as the previous LAGOS edition.
Unfortunately, the ENTCS publication by Elsevier has been discontinued as of 2021.

Following the ENTCS transition recommendation and also consulting the LAGOS Steering Committee, the LAGOS 2021 proceedings will be published in the Procedia Computer Science (PROCS series).

We apologize for any inconvenience this change may cause you.
The proceedings will be published by Elsevier after the conference and a preview of it was sent to the emails of the participants.

April 22, 2021

The final version of the program is available.

April 16, 2021

We are thrilled to announce two great news.
First, there will be a best paper award in this edition of LAGOS!
Second, LAGOS will be produced by Virtual Chair on the Gather platform.

April 14, 2021

A preliminary version of the program is available.

April 14, 2021

There will be a minicourse of 3 hours, given by prof. Marcel Carli da Silva, about Some Discrete Aspects of Semidefinite Programming.

March 21, 2021

Registration is now open and the list of accepted papers is available.

November 23, 2020

After careful consideration, the Local Organizing Committee and the Steering Committee have decided that LAGOS 2021 will be held online.
It is unfortunate that we cannot meet in person, but we do expect to have a great event!

November 20, 2020

All authors interested in participating in LAGOS 2021 must submit a preliminary version of the paper until November 25, 2020.
This version must contain a good presentation of problems investigated, main results obtained and approaches used.
The paper can be updated until November 29, 2020.
The acceptance or rejection of the paper will be based on the last version that was submitted.

November 9, 2020

We are monitoring the Coronavirus outbreak situation.
We have not yet discarded the possibility of doing a physical conference, but in any case we will allow remote participation.

ps.: Submission deadline was postponed to November 25!

Awards 🏆

The papers presented at the conference were considered for the Best Paper Award.

The 3rd place Best Paper Award was conferred to Luis Gustavo Da Soledade Gonzaga, Sheila Almeida, Cândida Nunes Da Silva and Jadder Bismarck Sousa Cruz, for the paper The chromatic index of split-interval graphs.

The 2nd place Best Paper Award was conferred to Peter Allen, Julia Böttcher, Ewan Davies, Eng Keat Hng and Jozef Skokan, for the paper An approximate blow-up lemma for sparse hypergraphs.

The Best Paper Award was conferred to Simón Piga and Nicolás Sanhueza-Matamala, for the paper Codegree conditions for cycle decompositions and Euler tours in 3-uniform hypergraphs.

Heartfelt congratulations to all the awardees!

Certificate of first place
Certificate of second place
Certificate of third place


Times in the program are shown in BRT Time (UTC -3).

See the full program here

May 17


  • 9 am Getting to know the system
  • 9:30 am Opening
  • 10 am Technical sessions 1 and 2
  • 11 am Extra Q&A
  • 11:15 am Plenary lecture: Jose R. Correa
  • 12:15 pm Lunch break
  • 2 pm Plenary lecture: Xingxing Yu
  • 3 pm Break
  • 3:15 pm Technical sessions 3 and 4
  • 4:35 pm Extra Q&A

May 18


  • 10 am Technical sessions 5 and 6
  • 11 am Extra Q&A
  • 11:15 am Plenary lecture: Silvano Martello
  • 12:15 pm Lunch break
  • 1 pm Minicourse
  • 2 pm Plenary lecture: Joseph S. B. Mitchell
  • 3 pm Break
  • 3:15 pm Technical sessions 7 and 8
  • 4:35 pm Extra Q&A

May 19


  • 10 am Technical sessions 9 and 10
  • 11 am Extra Q&A
  • 11:15 am Plenary lecture: Laura SanitĂ 
  • 12:15 pm Official photo 📸
  • 12:30 pm Lunch break
  • 1 pm Minicourse
  • 2 pm Plenary lecture: Kirk Pruhs
  • 3 pm Break
  • 3:15 pm Technical sessions 11 and 12
  • 4:35 pm Extra Q&A

May 20


  • 10 am Technical sessions 13 and 14
  • 11 am Extra Q&A
  • 11:15 am Plenary lecture: Jayme L. Szwarcfiter
  • 12:15 pm Lunch break
  • 1 pm Minicourse
  • 2 pm Plenary lecture: Eduardo Uchoa
  • 3 pm Break
  • 3:15 pm Technical sessions 15 and 16
  • 4:15 pm Extra Q&A

May 21


  • 10 am Technical sessions 17 and 18
  • 11 am Extra Q&A
  • 11:15 am Plenary lecture: Kristina Vušković
  • 12:15 pm Lunch break
  • 2 pm Plenary lecture: Martin Grötschel
  • 3 pm Break
  • 3:15 pm Special session 🦉 Yoshiko Wakabayashi
  • 3:55 pm Best paper award 🏆
  • 4:15 pm Closing remarks
  • 4:35 pm Business meeting

Accepted papers

The proceedings of LAGOS 2021 are now available.

Kernelization results for equitable coloring Guilherme de Castro Mendes Gomes and Vinicius F. dos Santos
Target set selection with maximum activation time Lucas Keiler, Carlos Vinicius G. C. Lima, Ana Karolinna Maia, Rudini Sampaio and Ignasi Sau
On total coloring the direct product of complete graphs Diane Castonguay, Celina M. H. de Figueiredo, Luis A. B. Kowada, Caroline S. R. PatrĂŁo, Diana Sasaki and Mario Valencia-Pabon
The speed and threshold of the biased perfect matching game Ndiamé Ndiaye, Noah Brustle, Sarah Clusiau, Vishnu V. Narayan, Bruce Reed and Ben Seamone
Combinatorial properties for the green vehicle routing problem Matheus Diógenes Andrade and Fábio Luiz Usberti
On the inapproximability of the cable-trench problem Hugo Kooki Kasuya Rosado, Marcelo Pinheiro Leite Benedito and Lehilton Lelis Chaves Pedrosa
Tromino tilings with pegs via flow networks Javier Akagi, Eduardo Canale and Marcos Villagra
Bounds on the diameter of graph associahedra Jean Cardinal, Lionel Pournin and Mario Valencia-Pabon
Partitioning into prescribed number of cycles and mod k T-join with slack Salomon Bendayan, Yanjia Li, Bruce Reed and Jordan Barrett
Unique maximum independent sets in graphs on monomials of a fixed degree John Machacek
The speed and threshold of the biased Hamilton cycle game Ndiamé Ndiaye, Noah Brüstle, Sarah Clusiau, Bruce Reed, Ben Seamone and Vishnu V. Narayan
Treelength of series-parallel graphs Guillaume Ducoffe, Thomas Dissaux, Nicolas Nisse and Simon Nivelle
Instance optimal join size estimation Mahmoud Abo Khamis, Sungjin Im, Benjamin Moseley, Kirk Pruhs and Alireza Samadian
Diameter in linear time for constant-dimension median graphs Pierre Bergé and Michel Habib
Upper bounds on the boolean rank of kronecker products Ishay Haviv and Michal Parnas
Parameterized algorithms for locating-dominating sets Márcia R. Cappelle, Guilherme de Castro Mendes Gomes and Vinicius F. dos Santos
Biclique graphs of K3-free graphs and bipartite graphs Marina Groshaus and André L. P. Guedes
Effective heuristics for the perfect awareness problem Felipe de C. Pereira, Pedro J. de Rezende and Cid C. de Souza
An efficient parameterized approximation scheme for the star k-hub center Marcelo P. L. Benedito and Lehilton L. C. Pedrosa
Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling Antoine Genitrini, Martin PĂ©pin and Alfredo Viola
On the diameter of Schrijver graphs Adrián Pastine, Pablo Torres and Mario Valencia-Pabon
On structural parameterizations of the selective coloring problem Guilherme de Castro Mendes Gomes and Vinicius F. dos Santos
Codegree conditions for cycle decompositions and Euler tours in 3-uniform hypergraphs Simón Piga and Nicolás Sanhueza-Matamala
Local construction of connected plane subgraphs in graphs satisfying redundancy and coexistence Lucas Böltz, Benjamin Becker and Hannes Frey
Cycle factors in randomly perturbed graphs Julia Böttcher, Olaf Parczyk, Amedeo Sgueglia and Jozef Skokan
Hitting times for arc-disjoint arborescences in random digraph processes MaurĂ­cio Collares, Yoshiharu Kohayakawa, TaĂ­sa Martins, Roberto Parente and Victor Souza
On total coloring of 4-regular circulant graphs Mauro Nigro Alves Junior, Diana Sasaki and Matheus Adauto
Intersection models for 2-thin and proper 2-thin graphs Flavia Bonomo-Braberman and GastĂłn Brito
The chromatic index of split-interval graphs Luis Gustavo Da Soledade Gonzaga, Sheila Almeida, Cândida Nunes Da Silva and Jadder Bismarck Sousa Cruz
Valid inequalities and a branch-and-cut algorithm for the routing and spectrum allocation problem Marcelo Bianchetti and Javier Marenco
On equitable total coloring of snarks Isabel F. A. Gonçalves, Simone Dantas and Diana Sasaki
Tridiagonal maximum-entropy sampling and tridiagonal masks Hessa Al-Thani and Jon Lee
Complete immersions in graphs with independence number two and small forbidden subgraphs Daniel A. Quiroz
Survival for a Galton-Watson tree with cousin mergers Laura Eslava, Sarah Penington and Fiona Skerman
The (a,b)-monochromatic transversal game on biclique-hypergraphs of powers of paths and of powers of cycles Wilder Mendes, Simone Dantas and Sylvain Gravier
Reversal and transposition distance of genomes considering flexible intergenic regions Klairton Lima Brito, Andre Rodrigues Oliveira, Alexsandro Oliveira Alexandrino, Ulisses Dias and Zanoni Dias
On feedback vertex set in reducible flow hypergraphs Luerbio Faria, André L. P. Guedes and Lilian Markenzon
Minimum number of bends of paths of trees in a grid embedding Vitor T. F. de Luca, Fabiano Oliveira and Jayme Szwarcfiter
Counting orientations of graphs with no strongly connected tournaments Fábio Botler, Carlos Hoppen and Guilherme Mota
The 2-Decomposition conjecture for a new class of graphs Andrea Jiménez, Maycon Sambinelli, Fábio Botler and Yoshiko Wakabayashi
An approximate blow-up lemma for sparse hypergraphs Peter Allen, Julia Böttcher, Ewan Davies, Eng Keat Hng and Jozef Skokan
Cliques in exact distance powers of graphs of given maximum degree Florent Foucaud, Suchismita Mishra, Narayanan Narayanan, Reza Naserasr and Petru Valicov
A branch-and-price algorithm for the ring/ring problem CecĂ­lia Lescano OsĂłrio and Edna Hoshino
Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism Andrzej Lingas
Maximum number of r-edge-colorings such that all copies of Kk are rainbow Josefran de O. Bastos, Hanno Lefmann, Andy Oertel, Carlos Hoppen and Dionatan R. Schmidt
The signature matrix for 6-Pfaffian graphs Roberta Rasoviti Marques Costa Moço, Alberto Alexandre Assis Miranda and Cândida Nunes da Silva
Automating tree-like resolution in time no(log n) is ETH-Hard Susanna F. de Rezende
Turán density of cliques of order five in 3-uniform hypergraphs with quasirandom links Sören Berger, Simon Piga, Christian Reiher, Vojtěch Rödl and Mathias Schacht
Maximum size of r-cross t-intersecting families Pranshu Gupta, Yannick Mogge, Simon Piga and Bjarne SchĂĽlke
A new formulation for the weighted safe set problem Enrico Malaguti and Vagner Pedrotti
Graphs with two moplexes Clément Dallard, Robert Ganian, Meike Hatzel, Matjaž Krnc and Martin Milanič
Extending an integer formulation for the guillotine 2D bin packing problem Henrique Becker, Luciana Buriol and Olinto AraĂşjo
Constrained colourings of random graphs MaurĂ­cio Collares, Yoshiharu Kohayakawa, Carlos Moreira and Guilherme Mota
Polarity graphs and C4-free multipartite graphs Claudia Gonçalves, Emerson Monte Carmelo and Irene Nakaoka
Valid inequalities and complete characterizations of the 2-domination and the P3-hull number polytopes Manuela Blaum and Javier Marenco
How to detect whether Shor's algorithm succeeds against large integers without a quantum computer Daniel Bastos and Luis Kowada
Tutte's 3-flow conjecture for almost even graphs LĂ©o V. Peres and Ricardo Dahab
Recursive constructions of amoebas Adriana Hansberg, Amanda Montejano and Yair Caro
The crossing number of centrally symmetric complete geometric graphs Bernardo Abrego, Julia Dandurand and Silvia Fernandez

Invited speakers


Jose R. Correa

Universidad de Chile, Chile

Invited talk


Martin Grötschel

Berlin-Brandenburgische Akademie der Wissenschaften, Germany

Invited talk


Silvano Martello

UniversitĂ  di Bologna, Italy

Invited talk


Joseph S. B. Mitchell

The State University of New York at Stony Brook, USA

Invited talk


Kirk Pruhs

University of Pittsburgh, USA

Invited talk


Laura SanitĂ 

University of Waterloo, Canada/Eindhoven University of Technology, Netherlands

Invited talk


Jayme Luiz Szwarcfiter

Universidade Federal do Rio de Janeiro, Brazil

Invited talk


Eduardo Uchoa

Universidade Federal Fluminense, Brazil

Invited talk


Kristina Vušković

University of Leeds, United Kingdom

Invited talk


Xingxing Yu

Georgia Institute of Technology, USA

Invited talk


The XI LAGOS conference will be online from May 17 to 22, 2021, and registration is now open!

We look forward to having you in our conference!
The activities will take place from 10am to 5pm (BRT time).
A full schedule will be available soon on this webpage.

Registration is mandatory for all participants and it must be done until May 17.

Important! For each accepted paper, one registration must be made in the category "Authors", regardless of who is going to present it at the conference.
For example, even if John Doe is the sole author of two papers, two registrations must be made.

To register, you must have an account in the SBC ECOS system.
To create an account, click here.
The link for the registration page is here.

In case of any changes to the submitted registration or any problem, please contact the organizers.

Fees and payment deadlines

The payments are in the official currency of Brazil, the Brazilian Real (BRL).


  • BRL 600 (approx. 100 USD)
    up to May 3
  • BRL 900 (approx. 150 USD)
    from May 4


  • BRL 600 (approx. 100 USD)
    up to May 3
  • BRL 900 (approx. 150 USD)
    from May 4

Students and postdocs

  • BRL 300 (approx. 50 USD)
    up to May 3
  • BRL 450 (approx. 75 USD)
    from May 4

The price of the registration will be used to pay for the event proceedings, online systems, among other costs.
It covers attendance to all technical sessions, plenary talks, and the mini-course.
After the end of the event a complete financial statement will be available for the participants.

Payments will be accepted via credit card. Those who have a bank account in Brazil may also pay via "débito" or "boleto" up to May 13.

Cancellation policy

All cancellation and changes must be reported by May 10.


We are thrilled to announce that LAGOS 2021 will be produced by Virtual Chair on the Gather platform.


Authors are invited to submit original contributions in English with eight (8) single-column letter-size pages in the Elsevier ENTCS format. The submissions are expected to be fully self-contained (including references). In the case that the 8-page format is insufficient for the whole submission, authors are encouraged to place some of the material in an optional appendix. This appendix will not be published in the proceedings and hence should not be referenced within the body of the 8-page paper, but it will be used to evaluate the submission.

Simultaneous submission of papers to any other conference with published proceedings, as well as the submission of previously published papers, is not allowed. At least one author of each accepted papers must register for the conference to be included in the program.

The submission process must be completed electronically through EasyChair.


As in the last edition, the proceedings of LAGOS 2021 will be published by Elsevier in the ENTCS - Electronic Notes in Theoretical Computer Science series.

Special issue

Following the tradition of LAGOS, a special issue of Discrete Applied Mathematics will be prepared for LAGOS 2021 and all interested researchers will be invited to contribute to this special issue. If the submission to this special issue of DAM is an extended version of the LAGOS 2021 submission published in ENTCS, the contribution should differ substantially from the submission published in ENTCS (e.g., further results, material from the optional appendix, etc., can be added).

Check the call for papers for the conference and the call for papers of the special issue.

Se vocĂŞ Ă© pesquisador no estado de SĂŁo Paulo, veja a chamada para apoio coletivo.


Yoshiko Wakabayashi

She is a Full Professor at the Computer Science Department, University of SĂŁo Paulo, Brazil.
Obtained Master Degree in Applied Mathematics at the University of SĂŁo Paulo (1977) and Doctor Degree (Dr. re. nat.) in Applied Mathematics at the Universitaet Augsburg (1986), Germany.
Her research interests include combinatorial optimization, graph theory, algorithms and complexity.
Member of the Academy of Sciences of SĂŁo Paulo State (ACIESP) since 2012. Member of the National Order of the Scientific Merit, class "Comendador", since 2010 (awarded by the Brazilian Ministry of Science and Technology). Member of the Brazilian Academy of Sciences since 2019.

ps.: She is an owl lover.

Important dates

(All deadlines are AOE timezone.)


May 17-21, 2021
To be held online

Preliminary submission deadline

November 15, 2020
November 25, 2020

Final submission deadline

November 29, 2020

Notification of acceptance

February 15, 2021

Camera ready

March 15, 2021

Registration opening

March 22, 2021



LAGOS 2021 invites you to show support of this meeting through sponsorship opportunities.
Customization of sponsorships is available.
In case of interest, please, contact the organizers for more information.