Algorithms for subgraph complementation to some classes of graphs

DOI10.1016/J.IPL.2024.106530MaRDI QIDQ6663515zbMATH OpenFDO

Authors Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep

Publication date 14 January 2025

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106530

zbMATH Keywords

diamondkernelizationminimum degreestar graphssubgraph complementation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Subgraph complementation
• On subgraph complementation to \(H\)-free graphs
• On subgraph complementation to \(H\)-free Graphs
• Cutting a tree with subgraph complementation is hard, except for some small trees

Cites work

• A survey of parameterized algorithms and the complexity of edge modification
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Generalized split graphs and Ramsey numbers
• scientific article; zbMATH DE number 7725599 (Why is no real title available?)
• On subgraph complementation to \(H\)-free Graphs
• Parameterized algorithms
• Parameterized algorithms for deletion to (r,)-graphs
• Polynomial kernelization for removing induced claws and diamonds
• Proceedings of the 64th annual IEEE symposium on foundations of computer science, FOCS 2023, Santa Cruz, CA, USA, November 6--9, 2023
• Recent developments on graphs of bounded clique-width
• Subgraph complementation

Cited in

(3)

• On subgraph complementation to \(H\)-free graphs
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion

This page was built for publication: Algorithms for subgraph complementation to some classes of graphs

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