Skip to Main content Skip to Navigation
Conference papers

Properties of Random Graphs via Boltzmann Samplers

Abstract : This work is devoted to the understanding of properties of random graphs from graph classes with structural constraints. We propose a method that is based on the analysis of the behaviour of Boltzmann sampler algorithms, and may be used to obtain precise estimates for the maximum degree and maximum size of a biconnected block of a "typical'' member of the class in question. We illustrate how our method works on several graph classes, namely dissections and triangulations of convex polygons, embedded trees, and block and cactus graphs.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184800
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 5:00:26 PM
Last modification on : Thursday, May 27, 2021 - 1:54:05 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:18:45 PM

File

dmAH0112.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184800, version 1

Collections

Citation

Konstantinos Panagiotou, Andreas Weißl. Properties of Random Graphs via Boltzmann Samplers. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.171-182. ⟨hal-01184800⟩

Share

Metrics

Record views

246

Files downloads

1056