3 Search Results for "Bonichon, Nicolas"


Document
Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes

Authors: Jacopo Borga and Mickaël Maazoun

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)


Abstract
Baxter permutations, plane bipolar orientations, and a specific family of walks in the non-negative quadrant are well-known to be related to each other through several bijections. We introduce a further new family of discrete objects, called coalescent-walk processes, that are fundamental for our results. We relate these new objects with the other previously mentioned families introducing some new bijections. We prove joint Benjamini - Schramm convergence (both in the annealed and quenched sense) for uniform objects in the four families. Furthermore, we explicitly construct a new fractal random measure of the unit square, called the coalescent Baxter permuton and we show that it is the scaling limit (in the permuton sense) of uniform Baxter permutations. To prove the latter result, we study the scaling limit of the associated random coalescent-walk processes. We show that they converge in law to a continuous random coalescent-walk process encoded by a perturbed version of the Tanaka stochastic differential equation. This result has connections (to be explored in future projects) with the results of Gwynne, Holden, Sun (2016) on scaling limits (in the Peanosphere topology) of plane bipolar triangulations. We further prove some results that relate the limiting objects of the four families to each other, both in the local and scaling limit case.

Cite as

Jacopo Borga and Mickaël Maazoun. Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{borga_et_al:LIPIcs.AofA.2020.7,
  author =	{Borga, Jacopo and Maazoun, Micka\"{e}l},
  title =	{{Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.7},
  URN =		{urn:nbn:de:0030-drops-120370},
  doi =		{10.4230/LIPIcs.AofA.2020.7},
  annote =	{Keywords: Local and scaling limits, permutations, planar maps, random walks in cones}
}
Document
Enumerating Minimal Dominating Sets in Triangle-Free Graphs

Authors: Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a question of Kanté et al. Additionally, we show that deciding if a set of vertices of a bipartite graph can be completed into a minimal dominating set is a NP-complete problem.

Cite as

Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. Enumerating Minimal Dominating Sets in Triangle-Free Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.STACS.2019.16,
  author =	{Bonamy, Marthe and Defrain, Oscar and Heinrich, Marc and Raymond, Jean-Florent},
  title =	{{Enumerating Minimal Dominating Sets in Triangle-Free Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.16},
  URN =		{urn:nbn:de:0030-drops-102557},
  doi =		{10.4230/LIPIcs.STACS.2019.16},
  annote =	{Keywords: Enumeration algorithms, output-polynomial algorithms, minimal dominating set, triangle-free graphs, split graphs}
}
Document
Improved Routing on the Delaunay Triangulation

Authors: Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, and Michiel Smid

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)


Abstract
A geometric graph G=(P,E) is a set of points in the plane and edges between pairs of points, where the weight of an edge is equal to the Euclidean distance between its two endpoints. In local routing we find a path through G from a source vertex s to a destination vertex t, using only knowledge of the current vertex, its incident edges, and the locations of s and t. We present an algorithm for local routing on the Delaunay triangulation, and show that it finds a path between a source vertex s and a target vertex t that is not longer than 3.56|st|, improving the previous bound of 5.9|st|.

Cite as

Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, and Michiel Smid. Improved Routing on the Delaunay Triangulation. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{bonichon_et_al:LIPIcs.ESA.2018.22,
  author =	{Bonichon, Nicolas and Bose, Prosenjit and De Carufel, Jean-Lou and Despr\'{e}, Vincent and Hill, Darryl and Smid, Michiel},
  title =	{{Improved Routing on the Delaunay Triangulation}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.22},
  URN =		{urn:nbn:de:0030-drops-94857},
  doi =		{10.4230/LIPIcs.ESA.2018.22},
  annote =	{Keywords: Delaunay, local routing, geometric, graph}
}
  • Refine by Author
  • 1 Bonamy, Marthe
  • 1 Bonichon, Nicolas
  • 1 Borga, Jacopo
  • 1 Bose, Prosenjit
  • 1 De Carufel, Jean-Lou
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Mathematics of computing → Permutations and combinations
  • 1 Mathematics of computing → Probability and statistics
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Delaunay
  • 1 Enumeration algorithms
  • 1 Local and scaling limits
  • 1 geometric
  • 1 graph
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail