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

DOI10.1016/0020-0190(86)90143-2zbMath0587.68062MaRDI 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

sorting; networks; spanning trees; worst-case time complexity; minimum- weight perfect matching

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

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

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