Using shortcut edges to maximize the number of triangles in graphs

DOI10.1016/J.ORL.2015.09.003MaRDI QIDQ1785441zbMATH OpenOpenAlexFDO

Authors Sina Dehghani, MohammadAmin Fazli, Jafar Habibi, Sadra Yazdanbod

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2015.09.003

zbMATH Keywords

graphsapproximation algorithmNP-completetriangles

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60) Paths and cycles (05C38)

Recommendations

• Packing triangles in bounded degree graphs.
• Minimizing the number of triangular edges
• Packing triangles in low degree graphs and indifference graphs
• Packing triangles in low degree graphs and indifference graphs
• Algorithms – ESA 2004

Cites work

• scientific article; zbMATH DE number 5936982 (Why is no real title available?)
• A random graph model for massive graphs
• CHANGING OPINIONS IN A CHANGING WORLD: A NEW PERSPECTIVE IN SOCIOPHYSICS
• Collective dynamics of `small-world' networks
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Efficient algorithms for Eulerian extension and rural Postman
• Emergence of Scaling in Random Networks
• Enhancing the robustness of scale-free networks
• Exploring complex networks
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Kronecker graphs: an approach to modeling networks
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Minimizing the diameter of a network using shortcut edges
• On Eulerian extensions and their application to no-wait flowshop scheduling

Cited in

(4)

• Use of MAX-CUT for Ramsey Arrowing of Triangles
• Number of Shortest Paths in Triangular Grid for 1- and 2-Neighborhoods
• Improving the betweenness centrality of a node by adding links
• The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs

Describes a project that uses

Uses Software

• KronFit

This page was built for publication: Using shortcut edges to maximize the number of triangles in graphs

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