Affiliations: FME, University of Ljubljana, Aškerčeva 6, Ljubljana 1000, Slovenia. {darja.rupnik, janez.zerovnik}@fs.uni-lj.si, janez.zerovnik@imfm.si
Correspondence:
[†]
Address for correspondence: FME, University of Ljubljana, Aškerčeva 6, Ljubljana 1000, Slovenia
Note: [*] The research supported in part by the Research agency of Slovenia, ARRS.
Note: [‡] Part time researcher at Institute of mathematics, physics and mechanics, Jadranska 19, Ljubljana.
Abstract: Reliability Hosoya-Wiener polynomial for edge weighted graphs is defined, that can be used as a measure of reliability of a communication network. Each edge is assigned two weights, reliability and communication delay. Some basic properties are given and a recursive formula for the reliability Hosoya-Wiener polynomial of a rooted tree is proved that yields a linear time algorithm on weighted trees. On general graphs, the reliability Hosoya-Wiener polynomial can be computed in O(n3) time.
Keywords: communication network, reliability Hosoya-Wiener polynomial
