Using shortcut edges to maximize the number of triangles in graphs

DOI10.1016/j.orl.2015.09.003zbMath1408.90295OpenAlexW1644104870MaRDI QIDQ1785441

Sina Dehghani, Mohammad Amin 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

approximation algorithmgraphsNP-completetriangles

Mathematics Subject Classification ID

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

Related Items (1)

Improving the Betweenness Centrality of a Node by Adding Links

Uses Software

• KronFit

Cites Work

• Unnamed Item
• Unnamed Item
• Improved approximability and non-approximability results for graph diameter decreasing problems
• On Eulerian extensions and their application to no-wait flowshop scheduling
• Detecting high log-densities
• Emergence of Scaling in Random Networks
• A random graph model for massive graphs
• Minimizing the Diameter of a Network Using Shortcut Edges
• Enhancing the robustness of scale-free networks
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Efficient Algorithms for Eulerian Extension and Rural Postman
• Collective dynamics of ‘small-world’ networks
• Exploring complex networks
• CHANGING OPINIONS IN A CHANGING WORLD: A NEW PERSPECTIVE IN SOCIOPHYSICS

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