Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: AN EXACT PERFORMANCE BOUND FOR AN O(m + n) TIME GREEDY MATCHING PROCEDURE. | AN EXACT PERFORMANCE BOUND FOR AN O m n TIME GREEDY MATCHING PROCEDURE Andrew Shapira ECSE Department Rensselaer Polytechnic Institute Troy New York 12180 shapiraa@ Submitted July 20 1997 accepted October 15 1997. AMS Subject Classification 1991 . Primary 05C70. Secondary 68Q25 05C35 05C85 68R05 68R10. Key Words. Analysis of algorithms extremal problems greedy procedure matching algorithms matching heuristics maximum matching performance guarantees. Abstract. We prove an exact lower bound on Y G the size of the smallest matching that a certain O m n time greedy matching procedure may find for a given graph G with n vertices and m edges. The bound is precisely Erdos and Gallai s extremal function that gives the size of the smallest maximum matching over all graphs with n vertices and m edges. Thus the greedy procedure is optimal in the sense that when only n and m are specified no algorithm can be guaranteed to find a larger matching than the greedy procedure. The greedy procedure and augmenting path algorithms are seen to be complementary the greedy procedure finds a large matching for dense graphs while augmenting path algorithms are fast for sparse graphs. Well known hybrid algorithms consisting of the greedy procedure followed by an augmenting path algorithm are shown to be faster than the augmenting path algorithm alone. The lower bound on y G is a stronger version of Erdos and Gallai s result and so the proof of the lower bound is a new way of proving of Erdos and Gallai s result. THE ELECTRONIC .JOURNAL OF COMBINATORICS 4 1997 R25 1 1 Introduction The following procedure is sometimes recommended for finding a matching that is used as an initial matching by a maximum cardinality matching algorithm 10 . Start with the empty matching and repeat the following step until the graph has no edges remove all isolated vertices select a vertex v of minimum degree select a neighbor w of v that has minimum degree among v s neighbors add v w to the current .
