Maximizing the strong triadic closure in split graphs and proper interval graphs

DOI10.1016/j.dam.2020.05.035zbMath1446.05080arXiv1609.09433OpenAlexW2964183795MaRDI QIDQ2197407

Charis Papadopoulos, Athanasios L. Konstantinidis

Publication date: 31 August 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenesspolynomial-time algorithmsplit graphsproper interval graphsstrong triadic closure

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Structural parameterization of 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 ⋮ A survey of the studies on Gallai and anti-Gallai graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized algorithms for finding square roots
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• The clique-separator graph for chordal graphs
• Gallai graphs and anti-Gallai graphs
• Complement reducible graphs
• Trivially perfect graphs
• Applying modular decomposition to parameterized cluster editing problems
• Optimal greedy algorithms for indifference graphs
• Computing square roots of trivially perfect and threshold graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Bipartite roots of graphs
• Generalized Graph Clustering: Recognizing (p,q)-Cluster Graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Computing the Bandwidth of Interval Graphs
• Graph Classes: A Survey
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Reducibility among Combinatorial Problems
• Paths, Trees, and Flowers
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Tree decompositions and social graphs

This page was built for publication: Maximizing the strong triadic closure in split graphs and proper interval graphs