Premium
A 1‐matching blossom‐type algorithm for edge covering problems
Author(s) -
Murty Katta G.,
Perin Clovis
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120403
Subject(s) - matching (statistics) , edge cover , cover (algebra) , enhanced data rates for gsm evolution , mathematics , algorithm , combinatorics , computational complexity theory , undirected graph , time complexity , computer science , graph , artificial intelligence , mechanical engineering , statistics , engineering
We discuss an efficient primal‐dual algorithm for finding a minimum cost edge cover in an undirected network G with n nodes and m edges, which is based on the blossom algorithm for 1‐matching problems. We establish that its worst case computational complexity is O ( n 3 ), the same as that for blossom or primal algorithms for 1‐matching problems.