Minimum-weight two-connected spanning networks (Q582215)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4130204
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Minimum-weight two-connected spanning networks |
scientific article; zbMATH DE number 4130204 |
Statements
Minimum-weight two-connected spanning networks (English)
0 references
1990
0 references
Consider the problem of constructing a minimum-weight, two-connected network spanning all the points in a set V with symmetric nonnegative distance function satisfying the triangle inequality. The authors prove that the weight of an optimal traveling salesman cycle is no greater than 4/3 times the weight of an optimal two-connected solution, with examples which approach this bound arbitrarily closely. The results are extended to the variation of the problem where only a prespecified subset of points must be spanned.
0 references
spanning network
0 references
two-connectivity
0 references
minimum-weight, two-connected network
0 references
symmetric nonnegative distance function
0 references
optimal traveling salesman cycle
0 references
0 references
0 references
0 references
0.8732611536979675
0 references
0.8528419137001038
0 references
0.8478200435638428
0 references
0.8460124135017395
0 references
0.826187252998352
0 references
