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

DOI10.4230/LIPICS.ISAAC.2017.53MaRDI QIDQ5136273zbMATH OpenFDO

Authors Athanasios L. Konstantinidis, Charis Papadopoulos

Publication date 25 November 2020

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2017.53

zbMATH Keywords

NP-completenesspolynomial-time algorithmproper interval graphssplit graphsstrong triadic closure

Mathematics Subject Classification ID

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

Recommendations

• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Strong triadic closure in cographs and graphs of low maximum degree
• Strong triadic closure in cographs and graphs of low maximum degree

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Bipartite roots of graphs
• Complement reducible graphs
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Computing square roots of trivially perfect and threshold graphs
• Computing the Bandwidth of Interval Graphs
• Gallai graphs and anti-Gallai graphs
• Generalized graph clustering: recognizing (p,q)-cluster graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Networks, crowds and markets. Reasoning about a highly connected world.
• Optimal greedy algorithms for indifference graphs
• Parameterized algorithms for finding square roots
• Paths, Trees, and Flowers
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Reducibility among combinatorial problems
• Social and economic networks.
• The clique-separator graph for chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tree decompositions and social graphs
• Trivially perfect graphs

Cited in

(6)

• Relaxing the strong triadic closure problem for edge strength inference
• Parameterized aspects of strong subgraph closure
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Parameterized aspects of strong subgraph closure
• Strong triadic closure in cographs and graphs of low maximum degree
• Strong triadic closure in cographs and graphs of low maximum degree

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

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