Resilience of Partial k-tree Networks
dc.contributor.author | Mata-Montero, Erick | |
dc.date.accessioned | 2023-06-20T20:36:07Z | |
dc.date.available | 2023-06-20T20:36:07Z | |
dc.date.issued | 1989-10-20 | |
dc.description | 28 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 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. | en_US |
dc.identifier.uri | https://hdl.handle.net/1794/28438 | |
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 | partial 2-tree networks | en_US |
dc.subject | planar networks | en_US |
dc.subject | network resilience | en_US |
dc.title | Resilience of Partial k-tree Networks | en_US |
dc.type | Article | en_US |