Tight approximation ratio for Minimum Maximal Matching
From MaRDI portal
Publication:2293087
DOI10.1007/978-3-030-17953-3_14zbMath1436.90120arXiv1811.08506OpenAlexW2964108539MaRDI QIDQ2293087
Szymon Dudycz, Jan Marcinkowski, Mateusz Lewandowski
Publication date: 6 February 2020
Full work available at URL: https://arxiv.org/abs/1811.08506
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (4)
Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Max-min greedy matching problem: hardness for the adversary and fractional variant ⋮ Unnamed Item ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
This page was built for publication: Tight approximation ratio for Minimum Maximal Matching
