VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Broadcasting on cactus graphs
    Čevnik, Maja ; Žerovnik, Janez, 1958-
    Broadcasting is the process of dissemination of a message from one vertex (called originator) to all other vertices in the graph. This task is accomplished by placing a sequence of calls between ... neighboring vertices, where one call requires one unit of time and each call involves exactly two vertices. Each vertex can participate in one call per one unit of time. Determination of the broadcast time of a vertex x in arbitrary graph G is NP-complete. Problem can be solved in polynomial time for trees and some subclasses of cactus graphs. In this paper broadcasting in cactus graphs is studied. An algorithm that determines broadcast time of any originator with time complexity O(n) in k-restricted cactus graph (where k is constant) is given. Furthermore, another algorithm which calculates broadcast time for all vertices in k-restricted cactus graph within the same time complexity is outlined. The algorithm also provides an optimal broadcast scheme for every vertex. As a byproduct, broadcast center of a k-restricted cactus graph is computed.
    Vir: Journal of combinatorial optimization. - ISSN 1382-6905 (Vol. 33, iss. 1, Jan. 2017, str. 292-316)
    Vrsta gradiva - članek, sestavni del
    Leto - 2017
    Jezik - angleški
    COBISS.SI-ID - 14221851

    Povezava(-e):

    http://link.springer.com/article/10.1007%2Fs10878-015-9957-8
    DOI

vir: Journal of combinatorial optimization. - ISSN 1382-6905 (Vol. 33, iss. 1, Jan. 2017, str. 292-316)
loading ...
loading ...
loading ...

Vnos na polico