4 Search Results for "Asinowski, Andrei"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.99
Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number

Authors: Boris Klemz and Marie Diana Sieper

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Level Planarity, each level y is equipped with a partial order ≺_y on its vertices and in the desired drawing the left-to-right order of vertices on level y has to be a linear extension of ≺_y. Constrained Level Planarity is known to be a remarkably difficult problem: previous results by Klemz and Rote [ACM Trans. Alg.'19] and by Brückner and Rutter [SODA'17] imply that it remains NP-hard even when restricted to graphs whose tree-depth and feedback vertex set number are bounded by a constant and even when the instances are additionally required to be either proper, meaning that each edge spans two consecutive levels, or ordered, meaning that all given partial orders are total orders. In particular, these results rule out the existence of FPT-time (even XP-time) algorithms with respect to these and related graph parameters (unless P=NP). However, the parameterized complexity of Constrained Level Planarity with respect to the vertex cover number of the input graph remained open. In this paper, we show that Constrained Level Planarity can be solved in FPT-time when parameterized by the vertex cover number. In view of the previous intractability statements, our result is best-possible in several regards: a speed-up to polynomial time or a generalization to the aforementioned smaller graph parameters is not possible, even if restricting to proper or ordered instances.
Cite as

Boris Klemz and Marie Diana Sieper. Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 99:1-99:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{klemz_et_al:LIPIcs.ICALP.2024.99,
  author =	{Klemz, Boris and Sieper, Marie Diana},
  title =	{{Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{99:1--99:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.99},
  URN =		{urn:nbn:de:0030-drops-202428},
  doi =		{10.4230/LIPIcs.ICALP.2024.99},
  annote =	{Keywords: Parameterized Complexity, Graph Drawing, Planar Poset Diagram, Level Planarity, Constrained Level Planarity, Vertex Cover, FPT, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.1
On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution

Authors: Andrei Asinowski and Cyril Banderier

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

Abstract
In this article, we analyse the joint distribution of some given set of patterns in fundamental combinatorial structures such as words and random walks (directed lattice paths on ℤ²). Our method relies on a vectorial generalization of the classical kernel method, and on a matricial generalization of the autocorrelation polynomial (thus extending the univariate case of Guibas and Odlyzko). This gives access to the multivariate generating functions, for walks, meanders (walks constrained to be above the x-axis), and excursions (meanders constrained to end on the x-axis). We then demonstrate the power of our methods by obtaining closed-form expressions for an infinite family of models, in terms of simple combinatorial quantities. Finally, we prove that the joint distribution of the patterns in walks/bridges/excursions/meanders satisfies a multivariate Gaussian limit law.
Cite as

Andrei Asinowski and Cyril Banderier. On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution. 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. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{asinowski_et_al:LIPIcs.AofA.2020.1,
  author =	{Asinowski, Andrei and Banderier, Cyril},
  title =	{{On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{1:1--1:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.1},
  URN =		{urn:nbn:de:0030-drops-120317},
  doi =		{10.4230/LIPIcs.AofA.2020.1},
  annote =	{Keywords: Lattice path, Dyck path, Motzkin path, generating function, algebraic function, kernel method, context-free grammar, multivariate Gaussian distribution}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.10
Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem

Authors: Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
In a companion article dedicated to the enumeration aspects, we showed how to obtain closed form formulas for the generating functions of walks, bridges, meanders, and excursions avoiding any fixed word (a pattern p). The autocorrelation polynomial of this forbidden pattern p (as introduced by Guibas and Odlyzko in 1981, in the context of regular expressions) plays a crucial role. In this article, we get the asymptotics of these walks. We also introduce a trivariate generating function (length, final altitude, number of occurrences of p), for which we derive a closed form. We prove that the number of occurrences of p is normally distributed: This is what Flajolet and Sedgewick call an instance of Borges's theorem. We thus extend and refine the study by Banderier and Flajolet in 2002 on lattice paths, and we unify several dozens of articles which investigated patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. Our approach relies on methods of analytic combinatorics, and on a matricial generalization of the kernel method. The situation is much more involved than in the Banderier-Flajolet work: forbidden patterns lead to a wider zoology of asymptotic behaviours, and we classify them according to the geometry of a Newton polygon associated with these constrained walks, and we analyse what are the universal phenomena common to all these models of lattice paths avoiding a pattern.
Cite as

Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger. Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{asinowski_et_al:LIPIcs.AofA.2018.10,
  author =	{Asinowski, Andrei and Bacher, Axel and Banderier, Cyril and Gittenberger, Bernhard},
  title =	{{Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotic Aspects and Borges's Theorem}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.10},
  URN =		{urn:nbn:de:0030-drops-89035},
  doi =		{10.4230/LIPIcs.AofA.2018.10},
  annote =	{Keywords: Lattice paths, pattern avoidance, finite automata, context-free languages, autocorrelation, generating function, kernel method, asymptotic analysis, Gaussian limit law}
}
Document
DOI: 10.4230/DagSemProc.06201.9
Suballowable sequences of permutations

Authors: Andrei Asinowski

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract
We discuss a notion of "allowable sequence of permutations" and show a few combinatorial results and geometric applications.
Cite as

Andrei Asinowski. Suballowable sequences of permutations. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{asinowski:DagSemProc.06201.9,
  author =	{Asinowski, Andrei},
  title =	{{Suballowable sequences of permutations}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.9},
  URN =		{urn:nbn:de:0030-drops-7833},
  doi =		{10.4230/DagSemProc.06201.9},
  annote =	{Keywords: Aequences of permutations}
}
  • Refine by Author
  • 3 Asinowski, Andrei
  • 2 Banderier, Cyril
  • 1 Bacher, Axel
  • 1 Gittenberger, Bernhard
  • 1 Klemz, Boris
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Distribution functions
  • 2 Mathematics of computing → Generating functions
  • 2 Theory of computation → Grammars and context-free languages
  • 2 Theory of computation → Random walks and Markov chains
  • 1 Human-centered computing → Graph drawings
  • Show More...

  • Refine by Keyword
  • 2 generating function
  • 2 kernel method
  • 1 Aequences of permutations
  • 1 Computational Geometry
  • 1 Constrained Level Planarity
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2006
  • 1 2018
  • 1 2020
  • 1 2024

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact