(Sub)linear kernels for edge modification problems toward structured graph classes
From MaRDI portal
Publication:2093576
DOI10.1007/S00453-022-00969-1OpenAlexW4225406559MaRDI QIDQ2093576
Nicolas Bousquet, Théo Pierron, Yixin Cao, Gabriel Bathie, Yuping Ke
Publication date: 27 October 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.09566
Related Items (1)
Cites Work
- Unnamed Item
- A \(2k\) kernel for the cluster editing problem
- Correlation clustering
- Cluster editing with locally bounded modifications
- The splittance of a graph
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Parameterizing edge modification problems above lower bounds
- Cluster editing: kernelization based on edge cuts
- A polynomial kernel for trivially perfect editing
- Quasi-threshold graphs
- A golden ratio parameterized algorithm for cluster editing
- Edge deletion problems: branching facilitated by modular decomposition
- Faster parameterized algorithms for deletion to split graphs
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- NP-completeness results for edge modification problems
- Exploring the Subexponential Complexity of Completion Problems
- Editing Simple Graphs
- The Comparability Graph of a Tree
- Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
- Kernelization
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Node-and edge-deletion NP-complete problems
- Parameterized Algorithms
- On the relation of strong triadic closure and cluster deletion
- Strong triadic closure in cographs and graphs of low maximum degree
- On the complexity of \(k\)-SAT
- Complexity classification of some edge modification problems
This page was built for publication: (Sub)linear kernels for edge modification problems toward structured graph classes
