Resilience of Partial k-tree Networks with Edge and Node Failures
Loading...
Date
1989-10-20
Authors
Mata-Montero, Erick
Journal Title
Journal ISSN
Volume Title
Publisher
University of Oregon
Abstract
The resilience of a network is the expected number of pairs of nodes
that can communicate. Computing the resilience of a network is a #P-complete
problem even for planar networks with fail-safe nodes. We generalize
an O(n)^2 time algorithm to compute the resilience of n-node k-tree
networks with fail-safe nodes to obtain an O(n) time algorithm that computes
the resilience of n-node partial k-tree networks with edge and node
failures (given a fixed k and an embedding of the partial k-tree in a k-tree).
Description
23 pages
Keywords
planar networks, fail-safe nodes, network resilience