Properties of Random Graphs via Boltzmann Samplers
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2007-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3552/pdf |
| _version_ | 1797270413587251200 |
|---|---|
| author | Konstantinos Panagiotou Andreas Weißl |
| author_facet | Konstantinos Panagiotou Andreas Weißl |
| author_sort | Konstantinos Panagiotou |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:53Z |
| format | Article |
| id | doaj.art-523351b79064460b8e308f3e370ded90 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:53Z |
| publishDate | 2007-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-523351b79064460b8e308f3e370ded902024-03-07T14:34:52ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502007-01-01DMTCS Proceedings vol. AH,...Proceedings10.46298/dmtcs.35523552Properties of Random Graphs via Boltzmann SamplersKonstantinos Panagiotou0Andreas WeißlInstitute of Theoretical Computer Science [Zurich]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.https://dmtcs.episciences.org/3552/pdfrandom graphs with structural constraintsgenerating functionssampling algorithms[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co][info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| spellingShingle | Konstantinos Panagiotou Andreas Weißl Properties of Random Graphs via Boltzmann Samplers Discrete Mathematics & Theoretical Computer Science random graphs with structural constraints generating functions sampling algorithms [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| title | Properties of Random Graphs via Boltzmann Samplers |
| title_full | Properties of Random Graphs via Boltzmann Samplers |
| title_fullStr | Properties of Random Graphs via Boltzmann Samplers |
| title_full_unstemmed | Properties of Random Graphs via Boltzmann Samplers |
| title_short | Properties of Random Graphs via Boltzmann Samplers |
| title_sort | properties of random graphs via boltzmann samplers |
| topic | random graphs with structural constraints generating functions sampling algorithms [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| url | https://dmtcs.episciences.org/3552/pdf |
| work_keys_str_mv | AT konstantinospanagiotou propertiesofrandomgraphsviaboltzmannsamplers AT andreasweißl propertiesofrandomgraphsviaboltzmannsamplers |