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 | |||||
|
|||||
CZU: 510.51+519.7 | |||||
MSC 2010: 68R10, 68Q25, 05C35, 05C05. | |||||
Pag. 3-14 | |||||
|
|||||
Descarcă PDF | |||||
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">