About this Mathematics article
Heuristic Enhancements of the Search for the Generation of All Perfect Matchings by M.M. Balakrishnarajan; P. Venuvanalingam is a Mathematics article available to read on EtoBox.
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.
It is typically read by researchers, students, and practitioners in Mathematics.
- Author
- M.M. Balakrishnarajan; P. Venuvanalingam
- Publisher
- Elsevier Science; Elsevier ; Elsevier Ltd.; Elsevier BV (ISSN 0893-9659)
- Published
- 1996
- Language
- EN
- Field
- Mathematics (Physical Sciences)