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
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)
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