A Tight Analysis of the Mazimal Matching Heuristic

摘要：

We study the worst-case performance of the maximal matching heuristic applied to the Minimum Vertex Cover and Minimum Maximal Matching problems, through a careful analysis of tight examples. We show that the tight worst-case approximation ratio is asymptotic to min2,1/(1-√1-∈) for graphs with an average degree at least en and to min2,1/∈ for graphs with a minimum degree at least en.

作者: Jean Cardinal Martine Labbe Stefan Langerman Eythan Levy Hadrien Melot

作者单位: Universite Libre de Bruxelles, Brussels, Belgium Universite de Mons-Hainaut, Belgium

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 701-709

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）