𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Heuristic enhancements of the search for the generation of all perfect matchings

✍ Scribed by M.M. Balakrishnarajan; P. Venuvanalingam

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
313 KB
Volume
9
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

A search based algorithm has been introduced by us [1] to generate all perfect matchings on a graph. This paper presents a modified search that employs novel heuristics for rapid generation. This is done by an intelligent selection of edges for generating the branch nodes of the associated semantic tree. A priori time complexity of the algorithm is nonlinear with respect to output size even after the implementation of these heuristics, but it ensures generation of the optimal search tree in O(c * e log v) time. This drastically reduces the time requirements, without compromising O(e) space complexity of the algorithm.

πŸ“œ SIMILAR VOLUMES

A survey of heuristics for the weighted
A survey of heuristics for the weighted matching problem
✍ David Avis πŸ“‚ Article πŸ“… 1983 πŸ› John Wiley and Sons 🌐 English βš– 909 KB

This survey paper reviews results on heuristics for two weighted matching problems: matchings where the vertices are points in the plane and weights are Euclidean distances, and the assignment problem. Several heuristics are described in detail-and results are given for worst-case ratio bounds, abso

The externalities of Search 2.0: The flo
The externalities of Search 2.0: The flow of personal information in the drive for the perfect search engine
✍ Michael Zimmer πŸ“‚ Article πŸ“… 2008 πŸ› Wiley (John Wiley & Sons) 🌐 English βš– 104 KB

## Abstract Web search engines have emerged as a ubiquitous and vital tool for the successful navigation of the growing online informational sphere. As Google puts it, their goal is to β€œorganize the world's information and make it universally accessible and useful” and to create the β€œperfect search

Lagrangian heuristic for a class of the
Lagrangian heuristic for a class of the generalized assignment problems
✍ Igor Litvinchev; Miguel Mata; Socorro Rangel; Jania Saucedo πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 314 KB

A Lagrangian based heuristic is proposed for many-to-many assignment problems taking into account capacity limits for task and agents. A modified Lagrangian bound studied earlier by the authors is presented and a greedy heuristic is then applied to get a feasible Lagrangian-based solution. The latte