/Exposé en anglais/Talk in english/

*A tight local algorithm for the minimum dominating set problem in outerplanar graphs*

We present a deterministic local algorithm which computes a 5-approximation of a minimum dominating set on outerplanar graphs, and show that this is optimal. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed. This is joint work with Marthe Bonamy, Linda Cook and Carla Groenland.

*Limiting crossing numbers*

In this talk we will explain a set up which shows that the theory of graph limits introduced by Lovász et al. can be applied to intersection graphs of graph drawings. We consider a model of random, geodesic drawings of the complete bipartite graph Kn,n on the unit sphere and show that the intersection graphs form a convergent series (for n going to infinity). This talk is based on joint work with Marthe Bonamy and Bojan Mohar.

[Alexandra Wesole] (Simon Fraser University, Vancouver)

http://www.sfu.ca/~agwesole/

{Remarques/Remarks}

▼
Cet exposé sera enregistré, merci de désactiver votre webcam et micro si vous ne souhaitez pas apparaître sur l'enregistrement. Les échanges informels avant et après l'exposé, ainsi que les questions, ne seront pas enregistrés.

N'hésitez pas à venir un peu avant le début de l'exposé pour faire des tests (et discuter informellement). Nous auront également des discussions informelles post-GT.

À très bientôt,

Marthe & Jonathan

Retrouvez toutes les informations du GT dématérialisé sur https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE

▼
This presentation will be recorded, please deactivate your webcam and microphone if you do not wish to appear on the recording. Informal exchanges before and after the presentation, as well as questions, will not be recorded.

Do not hesitate to come a little before the start of the presentation to test (and chat informally). We will also have informal post-working group discussions.

See you soon,

Marthe & Jonathan

Find all the information of the dematerialized working group on the web page https://combalgo.labri.fr/pmwiki.php/Groupe/GT-en-LIGNE