On subgraph complementation to \(H\)-free Graphs

DOI10.1007/s00453-022-00991-3OpenAlexW3135535217MaRDI QIDQ2088585

Sagnik Sen, Jay Garchar, Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep, R. Subashini

Publication date: 6 October 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.02936

zbMATH Keywords

graph classesgraph modificationsubgraph complementation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Recent developments on graphs of bounded clique-width
• A more effective linear kernelization for cluster editing
• Generalized split graphs and Ramsey numbers
• Which problems have strongly exponential complexity?
• Cluster editing: kernelization based on edge cuts
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• Subgraph complementation
• Minimum fill-in: inapproximability and almost tight lower bounds
• Incompressibility of \(H\)-free edge modification problems
• On subgraph complementation to \(H\)-free graphs
• Edge-Deletion Problems
• Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
• On Switching to H‐Free Graphs
• Parameterized Algorithms
• Polynomial kernels for paw-free edge modification problems

This page was built for publication: On subgraph complementation to \(H\)-free Graphs