Skip to main content
Springer Nature Link
Log in

Increasing Diamonds

  • Conference paper
  • First Online:
LATIN 2016: Theoretical Informatics (LATIN 2016)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9644))

Included in the following conference series:

Abstract

A class of diamond-shaped combinatorial structures is studied whose enumerating generating functions satisfy differential equations of the form \(f'' = G(f)\), for some function G. In addition to their own interests and being natural extensions of increasing trees, the study of such DAG-structures was motivated by modelling executions of series-parallel concurrent processes; they may also be used in other digraph contexts having simultaneously a source and a sink, and are closely connected to a few other known combinatorial structures such as trees, cacti and permutations. We explore in this extended abstract the analytic-combinatorial aspect of these structures, as well as the algorithmic issues for efficiently generating random instances.

This research was partially supported by the ANR MetACOnc project ANR-15-CE40-0014.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

') var buybox = document.querySelector("[data-id=id_"+ timestamp +"]").parentNode var buyingOptions = buybox.querySelectorAll(".buying-option") ;[].slice.call(buyingOptions).forEach(initCollapsibles) // springerPlus roll out 10% starts here var springerPlusGroup = setLocalStorageSpringerPlus(); var rollOutSpringerPlus = springerPlusGroup === "B" function setLocalStorageSpringerPlus() { var selectUserKey = "springerPlusRollOut"; var springerPlusGroup = "X"; if (!window.localStorage) return springerPlusGroup; try { var selectUserValue = window.localStorage.getItem(selectUserKey) springerPlusGroup = selectUserValue || randomDistributionSpringerPlus(selectUserKey) } catch (err) { console.log(err) } return springerPlusGroup; } function randomDistributionSpringerPlus(selectUserKey) { var randomGroup = Math.random() < 0.7 ? "A" : "B" window.localStorage.setItem(selectUserKey, randomGroup) return randomGroup } if (rollOutSpringerPlus) { revealSpringerPlus(); } function revealSpringerPlus() { if(buybox) { document.querySelectorAll(".c-springer-plus").forEach(function(node) { node.style.display = "block" }) } } //springerPlus ends here var buyboxMaxSingleColumnWidth = 480 function initCollapsibles(subscription, index) { var toggle = subscription.querySelector(".buying-option-price") subscription.classList.remove("expanded") var form = subscription.querySelector(".buying-option-form") var priceInfo = subscription.querySelector(".price-info") var buyingOption = toggle.parentElement if (toggle && form && priceInfo) { toggle.setAttribute("role", "button") toggle.setAttribute("tabindex", "0") toggle.addEventListener("click", function (event) { var expandedBuyingOptions = buybox.querySelectorAll(".buying-option.expanded") var buyboxWidth = buybox.offsetWidth ;[].slice.call(expandedBuyingOptions).forEach(function(option) { if (buyboxWidth <= buyboxMaxSingleColumnWidth && option != buyingOption) { hideBuyingOption(option) } }) var expanded = toggle.getAttribute("aria-expanded") === "true" || false toggle.setAttribute("aria-expanded", !expanded) form.hidden = expanded if (!expanded) { buyingOption.classList.add("expanded") } else { buyingOption.classList.remove("expanded") } priceInfo.hidden = expanded }, false) } } function hideBuyingOption(buyingOption) { var toggle = buyingOption.querySelector(".buying-option-price") var form = buyingOption.querySelector(".buying-option-form") var priceInfo = buyingOption.querySelector(".price-info") toggle.setAttribute("aria-expanded", false) form.hidden = true buyingOption.classList.remove("expanded") priceInfo.hidden = true } function initKeyControls() { document.addEventListener("keydown", function (event) { if (document.activeElement.classList.contains("buying-option-price") && (event.code === "Space" || event.code === "Enter")) { if (document.activeElement) { event.preventDefault() document.activeElement.click() } } }, false) } function initialStateOpen() { var buyboxWidth = buybox.offsetWidth ;[].slice.call(buybox.querySelectorAll(".buying-option")).forEach(function (option, index) { var toggle = option.querySelector(".buying-option-price") var form = option.querySelector(".buying-option-form") var priceInfo = option.querySelector(".price-info") if (buyboxWidth > buyboxMaxSingleColumnWidth) { toggle.click() } else { if (index === 0) { toggle.click() } else { toggle.setAttribute("aria-expanded", "false") form.hidden = "hidden" priceInfo.hidden = "hidden" } } }) } initialStateOpen() if (window.buyboxInitialised) return window.buyboxInitialised = true initKeyControls() })()

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    We limit our discussion in this paper to the situation when \(f'(0)=1\) for simplicity.

References

  1. Abramowitz, M., Stegun, I.: Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables. Dover Publications, New York (2012)

    MATH  Google Scholar 

  2. Ando, E., Nakata, T., Yamashita, M.: Approximating the longest path length of a stochastic DAG by a normal distribution in linear time. J. Discrete Algorithms 7(4), 420–438 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bergeron, F., Flajolet, P., Salvy, B.: Varieties of increasing trees. In: Raoult, J.-C. (ed.) CAAP ’92. LNCS, vol. 581, pp. 24–48. Springer, Heidelberg (1992)

    Chapter  Google Scholar 

  4. Bodini, O.: Autour de la génération aléatoire sous modèle de Boltzmann. Habilitation thesis, UPMC (2010)

    Google Scholar 

  5. Bodini, O., Roussel, O., Soria, M.: Boltzmann samplers for first-order differential specifications. Discrete Appl. Math. 160(18), 2563–2572 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chern, H.-H., Fernández-Camacho, M.-I., Hwang, H.-K., Martínez, C.: Psi-series method for equality of random trees and quadratic convolution recurrences. Random Struct. Algorithms 44(1), 67–108 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  7. Duchon, P., Flajolet, P., Louchard, G., Schaeffer, G.: Boltzmann samplers for the random generation of combinatorial structures. Comb. Prob. Comput. 13(4–5), 577–625 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  8. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)

    Book  MATH  Google Scholar 

  9. Knuth, D.E.: The Art of Computer Programming, volume 1 (3rd ed.): Fundamental Algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA (1997)

    Google Scholar 

  10. Kuba, M., Panholzer, A.: A combinatorial approach to the analysis of bucket recursive trees. Theor. Comput. Sci. 411(34–36), 3255–3273 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Kuba, M., Panholzer, A.: Bilabelled increasing trees and hook-length formulae. Eur. J. Combin. 33(2), 248–258 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  12. Kuba, M., Panholzer, A.: Combinatorial families of multilabelled increasing trees and hook-length formulas. Discrete Math. 339, 227–254 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  13. Meir, A., Moon, J.W.: On the altitude of nodes in random trees. Can. J. Math. 30(5), 997–1015 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  14. Stanley, R.: Catalan Numbers. Cambridge University Press, Cambridge (2015)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratoire d’Informatique de Paris-Nord, CNRS UMR 7030 - Institut Galilée - Université Paris-Nord, 99, Avenue Jean-Baptiste Clément, 93430, Villetaneuse, France

    Olivier Bodini & Xavier Fontaine

  2. Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 Place Jussieu, 75005, Paris, France

    Matthieu Dien & Antoine Genitrini

  3. Institute of Statistical Science, Academia Sinica, Taipei, 115, Taiwan

    Hsien-Kuei Hwang

Authors
  1. Olivier Bodini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthieu Dien
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xavier Fontaine
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Antoine Genitrini
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Hsien-Kuei Hwang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Antoine Genitrini .

Editor information

Editors and Affiliations

  1. Carleton University, Ottawa, ON, Ontario, Canada

    Evangelos Kranakis

  2. University Chile, Santiago, Chile

    Gonzalo Navarro

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bodini, O., Dien, M., Fontaine, X., Genitrini, A., Hwang, HK. (2016). Increasing Diamonds. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-662-49529-2_16

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-662-49528-5

  • Online ISBN: 978-3-662-49529-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation