A 1‐matching blossom‐type algorithm for edge covering problems | Zendy

Murty Katta G. | Zendy; Perin Clovis | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research