Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Efficient Algorithms for Finding Maximal Matching in Graphs

IP.com Disclosure Number: IPCOM000127965D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 19 page(s) / 54K

Publishing Venue

Software Patent Institute

Related People

Zvi Galil: AUTHOR [+3]

Abstract

The paper surveys the techniques used for designing the most efficient algorithms for finding a maximal (cardinality or weighted) matching in (general or bipa rtite) graphs. it also lists some open problems concerning possible improvements and the existence of fast parallel algorithms for these problems. Key words: Shmathematics, algorithmic tools, data. structures, monsters, matching, polygamy, the asexual case, the assignment problem, moonlighting, augmenting path, ET, blossoms, shrink, The Main Theorem of Botany, The ACM Longest Paper Award, generalized priority queue, d-heap, warm-up, duality; primal-dual, sexual discrimination, affirmative action, joint income tax return.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Efficient Algorithms for Finding Maximal Matching in Graphs

Zvi Galil Columbia University and Tel-Aviv University

February 1983

Abstract:

The paper surveys the techniques used for designing the most efficient algorithms for finding a maximal (cardinality or weighted) matching in (general or bipa rtite) graphs. it also lists some open problems concerning possible improvements and the existence of fast parallel algorithms for these problems.

Key words: Shmathematics, algorithmic tools, data. structures, monsters, matching, polygamy, the asexual case, the assignment problem, moonlighting, augmenting path, ET, blossoms, shrink, The Main Theorem of Botany, The ACM Longest Paper Award, generalized priority queue, d-heap, warm-up, duality; primal-dual, sexual discrimination, affirmative action, joint income tax return.

Introduction.

There are no recipes for designing efficient algorithms. This is somewhat unfortunate from the point of view of appli-cations: Any time we have to design an algorithm, we may have to start (almost) from scratch. However, it is fortunate from the point of view of researchers. It is unlikely that we are going to run out of problems or challenges.

Given a problem, we want to find an algorithm that solves it efficiently. There are three stages in the design.

1. Shmathematics.

Initially we use some mathematical arguments to characterize the solution. The Mathematics used is usually quite simple ('sh' possibly for shallow). This leads to a simple algorithm that is usually not very efficient.

2. Algorithmic tools.

Next, we try to apply a number of algorithmic tools to speed up the algorithm. Examples of such tools are "divide and conquer" and dynamic programming [AHU]. Alternatively, we may try to find a way to reduce the number of steps in the original algorithm possibly by finding a better way to organize the information.

3. Data structures and monsters.

Sometimes we can speed.up, our algorithm by using an efficient data structure that supports the primitive operations that the algorithm uses. We may even resort to the introduction of

Columbia University Page 1 Dec 31, 1983

Page 2 of 19

Efficient Algorithms for Finding Maximal Matching in Graphs

monsters. These are very complicated data structures that bring about some asymptotic speed up, that usually becomes meaningful only for very large problem.size, (For a real-life monster see [Gal.) In these three.stages we sometimes use a known technique: a certain result in mathematics, say, or a known algorithmic tool or date structure. In the more interesting problems we need to invent new techniques, or to refine existing ones for our PurDoses. we may need to prove new Shmathematics; to find an appropriate way to organize information, or even how to use a known algorithmic tool; or to invent a new data structure or make some observations concerning known data structures that make them useful for our purpo...