A lower bound to the complexity of Euclidean and rectilinear matching algorithms (Q1072708): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1176565 |
Changed an Item |
||
Property / author | |||
Property / author: Michael D. Grigoriadis / rank | |||
Normal rank |
Revision as of 20:11, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A lower bound to the complexity of Euclidean and rectilinear matching algorithms |
scientific article |
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