ON NONTRIVIAL COVERS AND PARTITIONS OF GRAPHS BY CONVEX SETS
| dc.contributor.author | Buzatu, Radu | |
| dc.contributor.author | Cataranciuc, Sergiu | |
| dc.date.accessioned | 2018-12-19T13:01:46Z | |
| dc.date.available | 2018-12-19T13:01:46Z | |
| dc.date.issued | 2018 | |
| dc.description.abstract | In this paper we prove that it is NP-complete to decide whet- her 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 re- cursive formula that establishes the maximum nontrivial convex cover number of a tree. | en |
| dc.identifier.citation | BUZATU, R., CATARANCIUC, S. On Nontrivial Covers and Partitions of Graphs by Convex Sets. In: Сomputer Science Journal of Moldova. 2018. Nr. 1(76), pp. 3-14. ISSN 1561-4042 | en |
| dc.identifier.issn | 1561-4042 | |
| dc.identifier.uri | https://ibn.idsi.md/sites/default/files/imag_file/3-14.pdf | |
| dc.identifier.uri | https://msuir.usm.md/handle/123456789/1908 | |
| dc.language.iso | en | en |
| dc.publisher | Institutul de Matematică şi Informatică al Academiei de Ştiinţe a Moldovei | en |
| dc.subject | convexity | en |
| dc.subject | complexity | en |
| dc.subject | nontrivial convex cover | en |
| dc.subject | tree | en |
| dc.title | ON NONTRIVIAL COVERS AND PARTITIONS OF GRAPHS BY CONVEX SETS | en |
| dc.type | Article | en |