Constrained bipartite vertex cover: the easy kernel is essentially tight

DOI10.4230/LIPICS.STACS.2016.45zbMATH Open1388.68122OpenAlexW2295705054MaRDI QIDQ4601897FDOQ4601897

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

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

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)

Cited In (2)

• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Title not available (Why is that?)

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)