On minimum maximal distance-\(k\) matchings

DOI10.1016/j.endm.2016.11.011zbMath1355.68123OpenAlexW2915515624MaRDI QIDQ509288

Yury Kartynnik, Andrew Ryzhikov

Publication date: 9 February 2017

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

zbMATH Keywords

computational complexity\(k\)-equimatchable graphsminimum maximal distance-\(k\) matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Unnamed Item ⋮ On two extensions of equimatchable graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Approximability results for the maximum and minimum maximal induced matching problems
• NP-completeness of some generalizations of the maximum matching problem
• Computing independent sets in graphs with large girth
• On the Maximum Independent Set Problem in Subclasses of Planar Graphs
• Analytical approach to parallel repetition
• Computational Complexity

This page was built for publication: On minimum maximal distance-\(k\) matchings