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

DOI10.1016/j.dam.2020.05.035zbMath1446.05080arXiv1609.09433MaRDI 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-completeness; polynomial-time algorithm; split graphs; proper interval graphs; strong triadic closure

Mathematics Subject Classification ID

91D30: Social networks; opinion dynamics

05C75: Structural characterization of families of graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)