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

Inicio | ¿Qué es? | Contacto

English | Català

Consultar RECERCAT

Por comunidades y
colecciones Por fecha Por autores Por títulos Por temas (CDU)

Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Estadisticas

Del documento Todo RECERCAT

Mi RECERCAT

Entrar Alertas por correo-e

Directorio de otros repositorios

RECERCAT Principal > Universitat Politècnica de Catalunya > Documents de recerca > Visualizar documento

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/122032

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtiques
dc.contributor	Universitat Politècnica de Catalunya. GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics
dc.contributor.author	Drmota, Michael
dc.contributor.author	Ramos, Lander
dc.contributor.author	Requilé, Clément
dc.contributor.author	Rué Perna, Juan José
dc.date	2018
dc.identifier.citation	Drmota, M., Ramos, L., Requilé, C., Rue, J. Maximal independent sets and maximal matchings in series-parallel and related graph classes. A: International Conference on the Analysis of Algorithms. "29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)". Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 18:1-18:15.
dc.identifier.citation	978-3-95977-078-1
dc.identifier.citation	http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8911
dc.identifier.uri	http://hdl.handle.net/2117/122032
dc.language.iso	eng
dc.publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Matemàtiques i estadística
dc.subject	Combinatorial analysis
dc.subject	asymptotic enumeration
dc.subject	central limit laws
dc.subject	subcritical graph classes
dc.subject	maximal independent set
dc.subject	maximal matching
dc.subject	Anàlisi combinatòria
dc.title	Maximal independent sets and maximal matchings in series-parallel and related graph classes
dc.type	info:eu-repo/semantics/submittedVersion
dc.type	info:eu-repo/semantics/conferenceObject
dc.description.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 seriesparallel 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.

Mostrar el registro sencillo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Triangles in random cubic planar graphs

Requilé, Clément; Rué Perna, Juan José

Asymptotic study of subcritical graph classes

Drmota, Michael; Fusy, Éric; Kang, Mihyun; Kraus, Veronika; Rué Perna, Juan José

Subgraph statistics in subcritical graph classes

Drmota, Michael; Ramos Garrido, Lander; Rué Perna, Juan José

The HOM problem is EXPTIME-complete

Creus López, Carles; Gascón Caro, Adrià; Godoy Balil, Guillem; Ramos, Lander

Random planar maps and graphs with minimum degree two and three

Noy Serrano, Marcos; Ramos, Lander

Accesibilidad | Aviso legal | Política de Cookies | Documentos de uso interno

Coordinación

Patrocinio