Cut-threshold graphs (Q2277496)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Cut-threshold graphs |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Cut-threshold graphs |
scientific article |
Statements
Cut-threshold graphs (English)
0 references
1991
0 references
The authors study the structure of the networks in which connectedness and disconnectedness can be expressed by a threshold system. So the elements of the network have a certain ``destruction cost'' and an enemy can disconnect the network if and only if he pays a large enough price. The authors give polynomial algorithms for the recognition of such networks, and for the determination of the appropriate costs and threshold value.
0 references
cut-threshold graph
0 references
connectedness
0 references
disconnectedness
0 references
polynomial algorithms
0 references
