On the Maximum Uniquely Restricted Matching for Bipartite Graphs

DOI10.1016/j.endm.2011.05.059zbMath1268.68135OpenAlexW2033371793MaRDI QIDQ2840733

Sounaka Mishra

Publication date: 23 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2011.05.059

zbMATH Keywords

graph theorymatchingsapproximation algorithmsuniquely restricted matchings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Uniquely restricted matchings in subcubic graphs ⋮ Zero forcing number, constrained matchings and strong structural controllability ⋮ On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ On the complexity of minimum maximal uniquely restricted matching ⋮ Approximating maximum uniquely restricted matchings in bipartite graphs ⋮ Uniquely Restricted Matchings in Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Edge Dominating Sets in Graphs
• Ranks of zero patterns and sign patterns^*
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Uniquely restricted matchings

This page was built for publication: On the Maximum Uniquely Restricted Matching for Bipartite Graphs