2 Search Results for "Ramos, Lander"

Document
DOI: 10.4230/LIPIcs.AofA.2018.18
Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes

Authors: Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué

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

Abstract
We provide combinatorial decompositions as well as asymptotic tight estimates for two maximal parameters: the number and average size of maximal independent sets and maximal matchings in series-parallel graphs (and related graph classes) with n vertices. In particular, our results extend previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]. We also show that these two parameters converge to a central limit law.
Cite as

Michael Drmota, Lander Ramos, Clément Requilé, and Juanjo Rué. Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes. 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. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{drmota_et_al:LIPIcs.AofA.2018.18,
  author =	{Drmota, Michael and Ramos, Lander and Requil\'{e}, Cl\'{e}ment and Ru\'{e}, Juanjo},
  title =	{{Maximal Independent Sets and Maximal Matchings in Series-Parallel and Related Graph Classes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{18:1--18:15},
  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.18},
  URN =		{urn:nbn:de:0030-drops-89117},
  doi =		{10.4230/LIPIcs.AofA.2018.18},
  annote =	{Keywords: Asymptotic enumeration, central limit laws, subcritical graph classes, maximal independent set, maximal matching}
}
Document
DOI: 10.4230/LIPIcs.RTA.2011.51
First-Order Unification on Compressed Terms

Authors: Adrià Gascón, Sebastian Maneth, and Lander Ramos

Published in: LIPIcs, Volume 10, 22nd International Conference on Rewriting Techniques and Applications (RTA'11) (2011)

Abstract
Singleton Tree Grammars (STGs) have recently drawn considerable attention. They generalize the sharing of subtrees known from DAGs to sharing of connected subgraphs. This allows to obtain smaller in-memory representations of trees than with DAGs. In the past years some important tree algorithms were proved to perform efficiently (without decompression) over STGs; e.g., type checking, equivalence checking, and unification. We present a tool that implements an extension of the unification algorithm for STGs. This algorithm makes extensive use of equivalence checking. For the latter we implemented two variants, the classical exact one and a recent randomized one. Our experiments show that the randomized algorithm performs better. The running times are also compared to those of unification over uncompressed trees.
Cite as

Adrià Gascón, Sebastian Maneth, and Lander Ramos. First-Order Unification on Compressed Terms. In 22nd International Conference on Rewriting Techniques and Applications (RTA'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 10, pp. 51-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{gascon_et_al:LIPIcs.RTA.2011.51,
  author =	{Gasc\'{o}n, Adri\`{a} and Maneth, Sebastian and Ramos, Lander},
  title =	{{First-Order Unification on Compressed Terms}},
  booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
  pages =	{51--60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-30-9},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{10},
  editor =	{Schmidt-Schauss, Manfred},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2011.51},
  URN =		{urn:nbn:de:0030-drops-31263},
  doi =		{10.4230/LIPIcs.RTA.2011.51},
  annote =	{Keywords: unification, matching, grammars, compression, STG, system C++}
}
  • Refine by Author
  • 2 Ramos, Lander
  • 1 Drmota, Michael
  • 1 Gascón, Adrià
  • 1 Maneth, Sebastian
  • 1 Requilé, Clément
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Graph enumeration
  • 1 Mathematics of computing → Matchings and factors
  • 1 Mathematics of computing → Random graphs
  • Show More...

  • Refine by Keyword
  • 1 Asymptotic enumeration
  • 1 STG
  • 1 central limit laws
  • 1 compression
  • 1 grammars
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2018

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