Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
On the Computational Complexity of Optimization Convex Covering Problems of Graphs
Authors: Radu Buzatu
Keywords: NP-hardness, convex cover, convex partition, graph.
– 0.16 Mb
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:
60 A. Mateevici, MD-2009, Chi¸ sinˇ au, Republic of Moldova
E-mail:
Fulltext
– 0.16 Mb
Contents
- Hospital-Scale Chest X-Ray Database Visualization Using RAWGraph Technique
- Solving transportation problems with concave cost functions using genetic algorithms
- Total k-rainbow domination subdivision number in graphs
- Chromatic Spectrum of Ks-WORM Colorings of Kn*
- On the Computational Complexity of Optimization Convex Covering Problems of Graphs
- On α-spectral theory of a directed k-uniform hypergraph
- C. Gaindric - National Prize Laureate of Moldova
