Subgraph complementation

DOI10.1007/s00453-020-00677-8zbMath1439.05212arXiv1804.10920OpenAlexW2798301280MaRDI QIDQ2182091

Fedor V. Fomin, Torstein J. F. Strømme, Dimitrios M. Thilikos, Petr A. Golovach

Publication date: 21 May 2020

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

graph classesgraph editingsubgraph complementation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Subgraph complementation and minimum rank ⋮ On subgraph complementation to \(H\)-free graphs ⋮ Hamming distance between the strings generated by adjacency matrix of a subgraph complementary graph and their sum ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ On subgraph complementation to \(H\)-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing locally equivalent graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Recent developments on graphs of bounded clique-width
• The splittance of a graph
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Rank-width: algorithmic and structural results
• Rank-width and vertex-minors
• On the Hardness of Switching to a Small Number of Edges
• List Partitions
• Partial complementation of graphs
• On Switching to H‐Free Graphs
• Finding Branch-Decompositions and Rank-Decompositions
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Subgraph complementation