| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142271 | Operations Research Letters | 2015 | 6 Pages |
Abstract
In this paper, we consider the following problem: given an undirected graph G=(V,E)G=(V,E) and an integer kk, find I⊆V2I⊆V2 with |I|≤k|I|≤k in such a way that G′=(V,E∪I)G′=(V,E∪I) has the maximum number of triangles (a cycle of length 33). We first prove that this problem is NP-hard and then give an approximation algorithm for it.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sina Dehghani, Mohammad Amin Fazli, Jafar Habibi, Sadra Yazdanbod,