|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 2 of 11 found articles
| Title: |
A simple variant of node connectivity is NP-complete |
| Author: |
Ramarao, K. V. S. |
| Appeared in: |
International journal of computer mathematics |
| Paging: | Volume 20 (1986) nr. 3-4 pages 245-251 |
| Year: |
1986 |
| Contents: |
A simple variant of the node connectivity problem arises in the domain of network reliability. Here, break-up of a network into two components can be tolerated, but not into three or more components. We show that the problem of determining the minimum number of node/edge deletions that break a network into three or more components is a computationally hard problem, by proving that its decision-version is NP-Complete. In the process, we show that a closely related problem, which can be of interest in itself, is also NP-Complete. |
| Publisher: |
Taylor & Francis |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 2 of 11 found articles
| << previous | next >> |