Výsledky vyhledávání - "Lander Ramos"

Maximal independent sets and maximal matchings in series-parallel and related graph classes

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

Publikováno v: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname

The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover tre

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ed770f2d8ce78bb8b0bab9e68e834693
https://hdl.handle.net/2117/185282

Zobrazit plný text záznamu

Subgraph statistics in subcritical graph classes

Autor: Juanjo Rué, Lander Ramos, Michael Drmota

Publikováno v: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname

Let $H$ be a fixed graph and $\mathcal{G}$ a subcritical graph class. In this paper we show that the number of occurrences of $H$ (as a subgraph) in a uniformly at random graph of size $n$ in $\mathcal{G}$ follows a normal limiting distribution with

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f6a65a2bc153fad97946ee4ae4ea6383
https://doi.org/10.1002/rsa.20721

Zobrazit plný text záznamu

Random Planar Maps and Graphs with Minimum Degree Two and Three

Autor: Lander Ramos, Marc Noy

Publikováno v: The Electronic Journal of Combinatorics. 25

We find precise asymptotic estimates for the number of planar maps and graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the core of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c50dbd9eec24149947ab7102246a8c30
https://doi.org/10.37236/7640

Zobrazit plný text záznamu

Graphs with degree constraints

Autor: Lander Ramos, Élie de Panafieu

Publikováno v: ANALCO

Given a set D of nonnegative integers, we derive the asymptotic number of graphs with a givenvnumber of vertices, edges, and such that the degree of every vertex is in D. This generalizes existing results, such as the enumeration of graphs with a giv

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::85ba1d3d71a63d99c3b61f9fae10d61f
https://doi.org/10.1137/1.9781611974324.4

Zobrazit plný text záznamu

Excessively duplicating patterns represent non-regular languages

Autor: Guillem Godoy, Carles Creus, Lander Ramos

Publikováno v: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
Universitat Jaume I

A constrained term pattern s:@f represents the language of all instances of the term s satisfying the constraint @f. For each variable in s, this constraint specifies the language of its allowed substitutions. Regularity of languages represented by s

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::37c9854f73c791f1b90e14e272565c16
https://hdl.handle.net/2117/23504

Zobrazit plný text záznamu

Random planar graphs with minimum degree two and three

Autor: Marc Noy, Lander Ramos

Publikováno v: The Seventh European Conference on Combinatorics, Graph Theory and Applications ISBN: 9788876424748

The main goal of this paper is to enumerate planar graphs subject to a condition on the minimum degree δ. Asking for δ ≥ 1 is not very interesting, since a random planar graph only contains a constant number of isolated vertices. The condition δ

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::158ba69c5ffafbfd7ec78a5e0d4364fe
https://doi.org/10.1007/978-88-7642-475-5_41

Zobrazit plný text záznamu

The HOM problem is EXPTIME-complete

Autor: Adria Gascon Caro, Guillem Godoy, Lander Ramos, Carles Creus

Publikováno v: UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Recercat. Dipósit de la Recerca de Catalunya
instname

We define a new class of tree automata with constraints and prove decidability of the emptiness problem for this class in exponential time. As a consequence, we obtain several EXPTIME-completeness results for problems on images of regular tree langua

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9c2d09bc938a3748cdc555673471f9e3
http://hdl.handle.net/2117/19252

Zobrazit plný text záznamu

The HOM problem is decidable

Autor: Carme Àlvarez, Guillem Godoy, Omer Giménez, Lander Ramos

Publikováno v: STOC

We provide an algorithm that, given a tree homomorphism H and a regular tree language L represented by a tree automaton, determines whether H(L) is regular. This settles a question that has been open for a long time.Along the way, we develop new cons

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::a6b6649a3dc31d9d0f9ba7d65ace62e4
https://doi.org/10.1145/1806689.1806757

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání