A lower bound to the complexity of Euclidean and rectilinear matching algorithms (Q1072708)
From MaRDI portal
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