QA343 : Backup 2-Center problem on Some Graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2016
Authors:
Mahieh Pagheh [Author], [Supervisor], Jafar Fathali[Advisor]
Abstarct: In practice, uncertainties can play an influential role. The reliability model deals with the situation where servers may sometimes fail, and the clients originally allocated to these servers have to request service from functioning servers. Recently, Wang, Wu and Chao, proposed a new reliability-baxsed model, in which each server may fail with a given probability. Once a server fails, the other server will take full responsibility for the services. Under the assumption that the servers do not fail simultaneously, they consider the backup 2-center problem on a tree, which asks for deploying two servers at the vertices such that the expected value of the longest distance from any vertex to its closest functioning server is minimum. We apply the reliability-baxsed backup 2-center model proposed by Wang, Wu and Chao, to interval graphs and present an O(n) time algorithm. We show that the weighted backup 2-center on a path (resp. tree, cycle, unicyclic) graph can be computed in O(n) (resp. O(n log n), O(n2), O(n2 log n)) time, where n is the number of vertices, and the centers need not be at vertices.
Keywords:
#Backup 2-center #Interval graph #Path #Tree #Cycle Link
Keeping place: Central Library of Shahrood University
Visitor: