On Nontrivial Covers and Partitions of Graphs by Convex Sets
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
1097 13
Ultima descărcare din IBN:
2024-03-14 20:32
Căutarea după subiecte
similare conform CZU
510.51+519.7 (1)
Considerații fundamentale și generale ale matematicii (37)
Cibernetică matematică (93)
SM ISO690:2012
BUZATU, Radu, CATARANCIUC, Sergiu. On Nontrivial Covers and Partitions of Graphs by Convex Sets. In: Computer Science Journal of Moldova, 2018, nr. 1(76), pp. 3-14. ISSN 1561-4042.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Computer Science Journal of Moldova
Numărul 1(76) / 2018 / ISSN 1561-4042 /ISSNe 2587-4330

On Nontrivial Covers and Partitions of Graphs by Convex Sets

CZU: 510.51+519.7
MSC 2010: 68R10, 68Q25, 05C35, 05C05.

Pag. 3-14

Buzatu Radu, Cataranciuc Sergiu
 
Moldova State University
 
Disponibil în IBN: 4 mai 2018


Rezumat

In this paper we prove that it is NP-complete to decide whether a graph can be partitioned into nontrivial convex sets. We show that it can be verified in polynomial time whether a graph can be covered by nontrivial convex sets. Also, we propose a recursive formula that establishes the maximum nontrivial convex cover number of a tree.

Cuvinte-cheie
Convexity, complexity, nontrivial convex cover,

nontrivial convex partition, tree.