Paper Info
Title
Algorithms For K-Terminal Reliability Problems With Node Failures
Abstract
Consider a distributed processing system with a set K of sites that can either cooperate in computing a function or hold resources required by other sites. The system is implemented using a communication network with unreliable nodes. Two simplified reliability problems then arise. In the first problem, we are interested in computing the probability that every operational pair of sites in K can communicate with each other. This problem is known to be #P-complete. In the second problem, the sites in K are service centers. Our reliability measure is the probability that every operational site in the network is connected to at least one operational service center. In this paper, we define the class of t-polygon graphs, t greater-than-or-equal-to 3, as the intersection graphs of straight-line chords in a convex t-gon. Hence, any t-polygon graph is a circle graph. We show that both problems admit polynomial time solutions when the underlying graph of the network is restricted to a t-polygon graph, for a fixed t.
Year
DOI
Venue
1992
10.1002/net.3230220405
NETWORKS
Keywords
Field
DocType
polynomial time,distributed processing
Comparability graph,Modular decomposition,Circle graph,Forbidden graph characterization,Distance-hereditary graph,Voltage graph,Discrete mathematics,Mathematical optimization,Combinatorics,Interval graph,Algorithm,String graph,Mathematics
Journal
Volume
Issue
ISSN
22
4
0028-3045
Citations 
PageRank 
References 
6
0.56
9
Authors
1
Name
Order
Citations
PageRank
Ehab S. Elmallah110519.29