Strong triadic closure in cographs and graphs of low maximum degree

DOI10.1016/j.tcs.2018.05.012zbMath1395.68212OpenAlexW2803851338MaRDI QIDQ5915633

Athanasios L. Konstantinidis, Charis Papadopoulos, Stavros D. Nikolopoulos

Publication date: 8 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.05.012

zbMATH Keywords

bounded degree graphsNP-completenesspolynomial-time algorithmcographscluster deletionstrong triadic closure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (5)

On the relation of strong triadic closure and cluster deletion ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ (Sub)linear kernels for edge modification problems toward structured graph classes ⋮ A survey of the studies on Gallai and anti-Gallai graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized algorithms for finding square roots
• The cluster deletion problem for cographs
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Exact exponential algorithms.
• Correlation clustering
• Cluster editing with locally bounded modifications
• Gallai graphs and anti-Gallai graphs
• Complement reducible graphs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• Which problems have strongly exponential complexity?
• Cluster graph modification problems
• On Independence Domination
• A Linear Recognition Algorithm for Cographs
• Parameterized Algorithms
• Independence numbers of product graphs
• Strong triadic closure in cographs and graphs of low maximum degree

This page was built for publication: Strong triadic closure in cographs and graphs of low maximum degree