Relating dissociation, independence, and matchings

DOI10.1016/j.dam.2022.07.012zbMath1498.05202arXiv2202.01004OpenAlexW4293490188WikidataQ130479427 ScholiaQ130479427MaRDI QIDQ2081478

Felix Bock, Dieter Rautenbach, Johannes Pardey, Lucia Draque Penso

Publication date: 13 October 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2202.01004

zbMATH Keywords

matchingindependent setinduced matchingdissociation set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Relating the independence number and the dissociation number

Cites Work

• Unnamed Item
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• Blockers and transversals
• An improved approximation for maximum \(k\)-dependent set on bipartite graphs
• Minimum \(k\)-path vertex cover
• The complexity of dissociation set problems in graphs
• Parameterized algorithm for 3-path vertex cover
• On the vertex \(k\)-path cover
• Node-Deletion Problems on Bipartite Graphs
• Reducibility among Combinatorial Problems
• On the Kőnig‐Egerváry theorem for ‐paths

This page was built for publication: Relating dissociation, independence, and matchings