A generalized hypergreedy algorithm for weighted perfect matching |
| |
| Authors: | Celina Imielinska Bahman Kalantari |
| |
| Institution: | (1) Department of Electrical Engineering and Computer Science, Stevens Institute of Technology, 07030 Hoboken, NJ, USA;(2) Department of Computer Science, Rutger University, 08903 New Brunswick, NJ, USA |
| |
| Abstract: | We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log2
n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518. |
| |
| Keywords: | F 2 2 G 2 2 E 5 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
