Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-18T02:22:42.752Z 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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