A lower bound to the complexity of Euclidean and rectilinear matching algorithms (Q1072708)
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: A lower bound to the complexity of Euclidean and rectilinear matching algorithms |
scientific article; zbMATH DE number 3943047
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A lower bound to the complexity of Euclidean and rectilinear matching algorithms |
scientific article; zbMATH DE number 3943047 |
Statements
A lower bound to the complexity of Euclidean and rectilinear matching algorithms (English)
0 references
1986
0 references
The worst-case time complexity of any exact algorithm for the Euclidean or rectilinear minimum-weight perfect matching problem, which takes as input the list of coordinates of n points in \({\mathbb{R}}^ k\), is shown to be bounded below by the infimum of the worst-case time complexities of all algorithms which sort n real numbers. This result also applies to any heuristic algorithm for which the worst-case ratio of the weight of the approximate matching it produces to the weight of the optimal matching only depends upon n.
0 references
networks
0 references
sorting
0 references
spanning trees
0 references
worst-case time complexity
0 references
minimum- weight perfect matching
0 references
