Constrained bipartite vertex cover: the easy kernel is essentially tight

DOI10.4230/LIPICS.STACS.2016.45MaRDI QIDQ4601897zbMATH OpenOpenAlexFDO

Authors Bart M. P. Jansen

Publication date 24 January 2018

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.STACS.2016.45

zbMATH Keywords

kernel lower boundsconstrained bipartite vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 2044921
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Kernels for structural parameterizations of vertex cover -- case of small degree modulators
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Publication:4941917

Cited in

(2)

• scientific article; zbMATH DE number 2044921 (Why is no real title available?)
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms

This page was built for publication: Constrained bipartite vertex cover: the easy kernel is essentially tight

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601897)