Resilience of Partial k-tree Networks
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 has been
shown to be a #P-complete problem for planar networks and to take
O(n)^2 time for n-node partial 2-tree networks. We present an O(n) time
algorithm to compute the resilience of partial 2-tree networks on n-nodes,
and, for a fixed k, an O(n)^2 algorithm to compute the resilience of n-node
partial k-tree networks given with an embedding in a k-tree.
Description
28 pages
Keywords
partial 2-tree networks, planar networks, network resilience