(Sub)linear kernels for edge modification problems towards structured graph classes

DOI10.4230/LIPICS.IPEC.2021.8MaRDI QIDQ6192476zbMATH OpenFDO

Authors Gabriel Bathie, Nicolas Bousquet, Théo Pierron

Publication date 12 February 2024

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2021.8

zbMATH Keywords

(sub)linear kernelsgraph editingkernelizationsplit graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• (Sub)linear kernels for edge modification problems toward structured graph classes
• Two edge modification problems without polynomial kernels
• A more effective linear kernelization for cluster editing
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• A More Effective Linear Kernelization for Cluster Editing

Cited in

(3)

• (Sub)linear kernels for edge modification problems toward structured graph classes
• A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
• A cubic vertex-kernel for trivially perfect editing

This page was built for publication: (Sub)linear kernels for edge modification problems towards structured graph classes

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