On Nontrivial Covers and Partitions of Graphs by Convex Sets
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
1096 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.

Google Scholar Export

<meta name="citation_title" content="On Nontrivial Covers and Partitions of Graphs by Convex Sets">
<meta name="citation_author" content="Buzatu Radu">
<meta name="citation_author" content="Cataranciuc Sergiu">
<meta name="citation_publication_date" content="2018/03/31">
<meta name="citation_journal_title" content="Computer Science Journal of Moldova">
<meta name="citation_volume" content="76">
<meta name="citation_issue" content="1">
<meta name="citation_firstpage" content="3">
<meta name="citation_lastpage" content="14">
<meta name="citation_pdf_url" content="https://ibn.idsi.md/sites/default/files/imag_file/3-14.pdf">