Resilience of Partial k-tree Networks

Loading...
Thumbnail Image

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

Citation