Wyniki wyszukiwania - BazTech

1

Reliability Hosoya-Wiener Polynomial of Double Weighted Trees

Rupnik Poklukar D., Žerovnik J.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 4

447--456

EN

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.

2

Wide-diameter of Product Graphs

Erveš R., Žerovnik J.

Fundamenta Informaticae

|

2013

|

Vol. 125, nr 2

153--160

EN

The product graph B * F of graphs B and F is an interesting model in the design of large reliable networks. Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k internally disjoint paths of length at most d between any two distinct vertices in G. Denote by DWc the c-diameter of G and κ(G) the connectivity of G. We prove that DWa+b(B * F) £ ra(F) + DWb (B) + 1 for a ≤ κ(F) and b ≤ κ(B). The Rabin number rc(G) is the minimum integer d such that there are c internally disjoint paths of length at most d from any vertex v to any set of c vertices {v1, v2, ... , vc}.

3

Chinese postman problem with priority nodes

Kramberger T., Štrubelj G., Žerovnik J.

Foundations of Computing and Decision Sciences

|

2009

|

Vol. 34, No. 4

233-264

EN

A generalization of the Chinese Postman Problem is studied in which the delays at a subset of priority nodes are penalized in the cost function. As it is shown that the problem is NP-hard, two tour constructing heuristics are proposed, and their properties are studied. It is proved that one of the heuristics gives optimal solutions on a subset of instances with bounded cost of delays. The implementations of the heuristics are compared on several types of randomly generated instances.