Buzatu, Radu2020-11-022020-11-022020BUZATU, Radu. On the Computational Complexity of Optimization Convex Covering Problems of Graphs. In: Computer Science Journal of Moldova.2020, nr.2(83). pp. 187-200. ISSN 1561-4042.1561-4042https://msuir.usm.md/handle/123456789/3065In this paper we present further studies of convex covers and convex partitions of graphs. Let G be a finite simple graph. A set of vertices S of G is convex if all vertices lying on a shortest path between any pair of vertices of S are in S . If 3 ≤ | S | ≤ | X | − 1, then S is a nontrivial set. We prove that determining the minimum number of convex sets and the minimum number of nontrivial convex sets, which cover or partition a graph, is in general NP-hard. We also prove that it is NP-hard to determine the maximum number of nontrivial convex sets, which cover or partition a graph.enNP-hardnessconvex coverconvex partitiongraphArticle