|
|||||
|
|
Cut-threshold graphs |
|
| Authors: | Peter L Hammer and Fr d ric Maffray Maurice Queyranne |
| Institution: | a RUTCOR, Rutgers Center for Operations Research, Hill Center, Busch Campus, Rutgers University, New Brunswick, NJ 08903, USA b Faculty of Commerce and Business Administration, University of British Columbia, 2053 Main Mall, Vancouver, Canada, BC V6T 1Y8 c Laboratoire d'Automatique et d'Analyse des Systèmes du CNRS, 7 Avenue du Colonel Roche, 31077 Toulouse Cédex, France |
| Abstract: | We study the structure of the networks in which connectedness and disconnectedness can be expressed by a threshold system. This means that the elements of the network have a certain “destruction cost” and that the enemy can disconnect the network if and only if they pay a large enough price. We give polynomial algorithms for the recognition of such networks, and for the determination of the appropriate costs and threshold value. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |