Facultatea de Matematică şi Informatică / Faculty of Methematics and Informatics

Permanent URI for this communityhttps://msuir.usm.md/handle/123456789/12

Browse

Filters

20181

Settings

Start date: 2010Subject: search.filters.subject.complexity

Search Results

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    ON NONTRIVIAL COVERS AND PARTITIONS OF GRAPHS BY CONVEX SETS
    (Institutul de Matematică şi Informatică al Academiei de Ştiinţe a Moldovei, 2018) Buzatu, Radu; Cataranciuc, Sergiu
    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.