A lower bound to the complexity of Euclidean and rectilinear matching algorithms

DOI10.1016/0020-0190(86)90143-2zbMath0587.68062OpenAlexW2048659526MaRDI QIDQ1072708

Bahman Kalantari, Michael D. Grigoriadis

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90143-2

zbMATH Keywords

sortingnetworksspanning treesworst-case time complexityminimum- weight perfect matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (4)

On the existence of weak greedy matching heuristics ⋮ New primal and dual matching heuristics ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ A generalized hypergreedy algorithm for weighted perfect matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of heuristics for the weighted matching problem
• Heuristic matching for graphs satisfying the triangle inequality
• Decomposable searching problems I. Static-to-dynamic transformation
• On a Greedy Heuristic for Complete Matching
• Combinatorial Problems: Reductibility and Approximation
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: A lower bound to the complexity of Euclidean and rectilinear matching algorithms