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

Home | About RECERCAT | Contact

Català | Castellano

All of RECERCAT

By Communities &
Collections By Defense Date By Authors By Titles By Subject

This Collection

By Defense Date By Authors By Titles By Subject

Statistics

View Statistics All RECERCAT

My RECERCAT

Other repositories directory

RECERCAT Home > Universitat Politècnica de Catalunya > Documents de recerca > View document

To access the full text documents, please follow this link: 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.

Show simple item record

All of RECERCAT

This Collection

Statistics

My RECERCAT

Related documents

Other documents of the same author