On Nontrivial Covers and Partitions of Graphs by Convex Sets
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
149 9
Ultima descărcare din IBN:
2019-11-16 00:50
Căutarea după subiecte
similare conform CZU
510.51+519.7 (1)
Considerații fundamentale și generale ale matematicii (24)
Cibernetică matematică (63)
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
BibTeX
DataCite
Dublin Core
Computer Science Journal of Moldova
Numărul 1(76) / 2018 / ISSN 1561-4042

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
 
State University of Moldova
 
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 partition, tree.,

nontrivial convex cover