Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching

DOI10.1002/net.3230130104zbMath0503.68051OpenAlexW2167937495MaRDI QIDQ3969884

Kenneth J. Supowit, Edward M. Reingold

Publication date: 1983

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230130104

zbMATH Keywords

expected costs of the matchings found by various divide-and-conquer heuristic algorithmsexpected times

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Algorithms in computer science (68W99)

Related Items (6)

Linear-Time Approximation for Maximum Weight Matching ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ Mellin transforms and asymptotics: Harmonic sums ⋮ Heuristic methods and applications: A categorized survey ⋮ Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching ⋮ A partitioning algorithm for minimum weighted Euclidean matching

Cites Work

• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

This page was built for publication: Probabilistic analysis of divide‐and‐conquer heuristics for minimum weighted euclidean matching