Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Boltzmann Oracle for ...
Conference paper

Boltzmann Oracle for Combinatorial Systems

Carine Pivoteau (1), Bruno Salvy ORCID (2), Michèle Soria (1)
(1) Algorithmes, Programmes et Résolution
(2) Algorithms
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Proceedings
DOI
10.46298/dmtcs.3585
License
Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
French National Research Agency (ANR)
ANR-07-BLAN-0330
Génération Aléatoire : Modèles, Méthodes et Algorithmes
Indicators
698
Views
565
Downloads

Boltzmann Oracle for Combinatorial Systems

Carine Pivoteau (1), Bruno Salvy ORCID (2), Michèle Soria (1)
(1) Algorithmes, Programmes et Résolution
(2) Algorithms
Abstract
Boltzmann random generation applies to well-defined systems of recursive combinatorial equations. It relies on oracles giving values of the enumeration generating series inside their disk of convergence. We show that the combinatorial systems translate into numerical iteration schemes that provide such oracles. In particular, we give a fast oracle based on Newton iteration.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • Random generation
  • Boltzmann generation
  • combinatorics
  • Newton iteration
Cited by

Source: OpenCitations

  • Boltzmann samplers for first-order differential specifications

    Discrete Applied Mathematics

    Authors : Olivier Bodini ORCID, Olivier Roussel ORCID, Michèle Soria

    Journal reference : Volume 160, 2012, pp. 2563-2572

    DOI : 10.1016/j.dam.2012.05.022

  • Uniform random sampling of planar graphs in linear time

    Random Structures and Algorithms

    Authors : Éric Fusy ORCID

    Journal reference : Volume 35, 2009, pp. 464-522

    DOI : 10.1002/rsa.20275

  • Asymptotic Analysis and Random Sampling of Digitally Convex Polyominoes

    Lecture notes in computer science

    Authors : O. Bodini ORCID, Ph. Duchon, A. Jacquot, L. Mutafchiev

    Journal reference : Volume , 2013, pp. 95-106

    DOI : 10.1007/978-3-642-37067-0_9

  • Uniform Random Generation of Huge Metamodel Instances

    Lecture notes in computer science

    Authors : Alix Mougenot, Alexis Darrasse, Xavier Blanc ORCID, Michèle Soria

    Journal reference : Volume , 2009, pp. 130-145

    DOI : 10.1007/978-3-642-02674-4_10

  • Controlled non-uniform random generation of decomposable structures

    Theoretical Computer Science

    Authors : A. Denise ORCID, Y. Ponty ORCID, M. Termier

    Journal reference : Volume 411, 2010, pp. 3527-3552

    DOI : 10.1016/j.tcs.2010.05.010

  • Algorithms for combinatorial structures: Well-founded systems and Newton iterations

    arXiv (Cornell University)

    Authors : Carine Pivoteau, Bruno Salvy ORCID, Michèle Soria

    Journal reference : Volume 119, 2012, pp. 1711-1773

    DOI : 10.1016/j.jcta.2012.05.007
Preview
Loading PDF preview...