RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.28, n.2 (83), 2020/

On the Computational Complexity of Optimization Convex Covering Problems of Graphs

Authors: Radu Buzatu
Keywords: NP-hardness, convex cover, convex partition, graph.

Abstract

In 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\leq|S|\leq|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.

State University of Moldova
60 A. Mateevici, MD-2009, Chi¸ sinˇ au, Republic of Moldova
E-mail:

Fulltext

Adobe PDF document0.16 Mb