(Sub)linear kernels for edge modification problems toward structured graph classes
From MaRDI portal
Publication:2093576
DOI10.1007/S00453-022-00969-1OpenAlexW4225406559MaRDI QIDQ2093576FDOQ2093576
Authors: Gabriel Bathie, Nicolas Bousquet, Yixin Cao, Yuping Ke, Théo Pierron 
Publication date: 27 October 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.09566
Recommendations
- (Sub)linear kernels for edge modification problems towards structured graph classes
- Two edge modification problems without polynomial kernels
- Two edge modification problems without polynomial kernels
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
Cites Work
- Fixed-parameter tractability of graph modification problems for hereditary properties
- A golden ratio parameterized algorithm for cluster editing
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- A \(2k\) kernel for the cluster editing problem
- Correlation clustering
- Cluster editing with locally bounded modifications
- Parameterized algorithms
- On the complexity of \(k\)-SAT
- The Comparability Graph of a Tree
- Node-and edge-deletion NP-complete problems
- The splittance of a graph
- Quasi-threshold graphs
- Complexity classification of some edge modification problems
- NP-completeness results for edge modification problems
- Editing simple graphs
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Cluster editing: kernelization based on edge cuts
- Edge deletion problems: branching facilitated by modular decomposition
- Faster parameterized algorithms for deletion to split graphs
- Exploring the subexponential complexity of completion problems
- Kernelization. Theory of parameterized preprocessing
- Strong triadic closure in cographs and graphs of low maximum degree
- A cubic vertex-kernel for trivially perfect editing
Cited In (6)
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- A quasi-quadratic vertex-kernel for cograph edge editing
- A survey of parameterized algorithms and the complexity of edge modification
- (Sub)linear kernels for edge modification problems towards 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 toward structured graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093576)
