On the Complexity of Average Path length for Biological Networks and Patterns

Asif, W., Qureshi, A., Iqbal, M. & Rajarajan, M. (2014). On the Complexity of Average Path length for Biological Networks and Patterns. International Journal of Biomathematics, 7(4), doi: 10.1142/S1793524514500387

[img]
Preview
PDF - Accepted Version
Download (469kB) | Preview

Abstract

Path length calculation is a frequent requirement in studies related to graph theoretic problems such as genetics. Standard method to calculate average path length of a graph requires traversing all nodes in the graph repeatedly, which is computationally expensive for graphs containing large number of nodes. We propose a novel method to calculate average path length for graphs commonly required in the studies of genetics. The proposed method is computationally less expensive and less time consuming compared to standard method. In this paper, a mathematical formulation is provided that calculates Average Path Length for graphs commonly present in biological networks, at the cost of uniform time complexity, for different size of networks.

Item Type: Article
Additional Information: Electronic version of an article published as Waqar Asif et al, Int. J. Biomath., 07, 4, 2014, article number:1450038, http:dx.doi.org/ 10.1142/S1793524514500387 © copyright World Scientific Publishing Company, http://www.worldscientific.com/worldscinet/ijb
Uncontrolled Keywords: Reductionism, average path length, protein–protein interaction
Subjects: Q Science > QA Mathematics
Divisions: School of Engineering & Mathematical Sciences > Engineering
URI: http://openaccess.city.ac.uk/id/eprint/4482

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics