|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 2 van 11 gevonden artikelen
| Titel: |
A simple variant of node connectivity is NP-complete |
| Auteur: |
Ramarao, K. V. S. |
| Verschenen in: |
International journal of computer mathematics |
| Paginering: | Jaargang 20 (1986) nr. 3-4 pagina's 245-251 |
| Jaar: |
1986 |
| Inhoud: |
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. |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 2 van 11 gevonden artikelen
| << vorige | volgende >> |