Resilience of Partial k-tree Networks with Edge and Node Failures
| dc.contributor.author | Mata-Montero, Erick | |
| dc.date.accessioned | 2023-06-20T20:33:18Z | |
| dc.date.available | 2023-06-20T20:33:18Z | |
| dc.date.issued | 1989-10-20 | |
| dc.description | 23 pages | en_US |
| dc.description.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). | en_US |
| dc.identifier.uri | https://hdl.handle.net/1794/28437 | |
| dc.language.iso | en | en_US |
| dc.publisher | University of Oregon | en_US |
| dc.rights | Creative Commons BY-NC-ND 4.0-US | en_US |
| dc.subject | planar networks | en_US |
| dc.subject | fail-safe nodes | en_US |
| dc.subject | network resilience | en_US |
| dc.title | Resilience of Partial k-tree Networks with Edge and Node Failures | en_US |
| dc.type | Article | en_US |