Maximum Minimal Vertex Cover Parameterized by Vertex Cover
From MaRDI portal
Publication:4588848
DOI10.1137/16M109017XzbMath1380.68236MaRDI QIDQ4588848
Publication date: 2 November 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
approximation algorithm; vertex cover; parameterized algorithm; maximization problem; strong exponential-time hypothesis; SETH
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms