Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T04:55:38.449Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE COMBINATORICS OF BINARY SERIES-PARALLEL GRAPHS

Published online by Cambridge University Press:  09 March 2016

Micha Hofri ,
Chao Li  and
Hosam Mahmoud
Micha Hofri
Affiliation:
Department of Computer Science, Worcester Polytechnic Institute, Worcester, MA, USA
Chao Li
Affiliation:
Department of Computer Science, Worcester Polytechnic Institute, Worcester, MA, USA
Hosam Mahmoud
Affiliation:
Department of Statistics, The George Washington University, Washington, D.C., USA E-mail: hosam@guru.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Binary series-parallel (BSP) graphs have applications in transportation modeling, and exhibit interesting combinatorial properties. This work is limited to the second aspect. The BSP graphs of a given size – measured in edges – are enumerated. Under a uniform probability model, we investigate the asymptotic distribution of the order (number of vertices) and the asymptotic average length of a random walk (under different strategies) of large graphs of the same size. The systematic method throughout is to define the graphs, and the features we evaluate by a structural equation (equivalent to a regular expression). The structural equation is translated into an equation for a generating function, which is then analyzed.

Information

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 30 , Issue 2 , April 2016 , pp. 244 - 260
Copyright
Copyright © Cambridge University Press 2016 

References

1.Bodirsky, M., Giménez, O., Kang, M., & Noy, M. (2007). Enumeration and limit laws of series-parallel graphs. European Journal of Combinatorics 28: 2091–2105.Google Scholar
2.Hofri, M. (1995). Analysis of algorithms: computational methods & mathematical tools. New York: Oxford University Press.Google Scholar
3.Mahmoud, H.M. (2014). Some properties of binary series-parallel graphs. Probability in the Engineering and Informational Sciences 28: 565–572. doi: 10.1017/S0269964814000138.CrossRefGoogle Scholar
4.On-line Encyclopedia of Integer sequences. Accessed at www.oeis.orgGoogle Scholar
5.Sedgewick, R. & Flajolet, P. (2013). An introduction to the analysis of algorithms, 2nd edn., Upper Saddle Valley, New Jersey: Addison-Wesley.Google Scholar
6.Stanley, R. (1999). Enumerative combinatorics, Vol. 2. New York: Cambridge University Press.Google Scholar