A 1-matching blossom-type algorithm for edge covering problems

DOI10.1002/net.3230120403zbMath0493.68069OpenAlexW2071862730MaRDI QIDQ3956416

Clovis Perin, Katta G. Murty

Publication date: 1982

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230120403

zbMATH Keywords

undirected networkworst case computational complexityminimum cost edge cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Applications of graph theory to circuits and networks (94C15)

Related Items (9)

Forest covers and a polyhedral intersection theorem ⋮ Edge covering problem under hybrid uncertain environments ⋮ System of unbiased representatives for a collection of bicolorings ⋮ A unified approach to approximating partial covering problems ⋮ Approximability of the capacitated \(b\)-edge dominating set problem ⋮ Metabolic networks are NP-hard to reconstruct ⋮ Path hitting in acyclic graphs ⋮ Fuzzy minimum weight edge covering problem ⋮ Constrained weighted matchings and edge coverings in graphs

Cites Work

• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• Modification of Edmonds' maximum matching algorithm

This page was built for publication: A 1-matching blossom-type algorithm for edge covering problems