On Nontrivial Covers and Partitions of Graphs by Convex Sets

Buzatu Radu; Cataranciuc Sergiu

Conţinutul numărului revistei

Articolul precedent

Articolul urmator

1139

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ă (94)

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

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.

Crossref XML Export

<?xml version='1.0' encoding='utf-8'?>
<doi_batch version='4.3.7' xmlns='http://www.crossref.org/schema/4.3.7' xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xsi:schemaLocation='http://www.crossref.org/schema/4.3.7 http://www.crossref.org/schema/deposit/crossref4.3.7.xsd'>
<head>
<doi_batch_id>ibn-61945</doi_batch_id>
<timestamp>1714120679</timestamp>
<depositor>
<depositor_name>Information Society Development Instiute, Republic of Moldova</depositor_name>
<email_address>idsi@asm.md</email_address>
</depositor>
</head>
<body>
<journal>
<journal_metadata>
<full_title>Computer Science Journal of Moldova</full_title>
<issn media_type='print'>15614042</issn>
</journal_metadata>
<journal_issue>
<publication_date media_type='print'>
<year>2018</year>
</publication_date>
<issue>1(76)</issue>
</journal_issue>
<journal_article publication_type='full_text'><titles>
<title>On Nontrivial Covers and Partitions of Graphs by Convex Sets</title>
</titles>
<contributors>
<person_name sequence='first' contributor_role='author'>
<given_name>Radu</given_name>
<surname>Buzatu</surname>
</person_name>
<person_name sequence='additional' contributor_role='author'>
<given_name>Sergiu</given_name>
<surname>Cataranciuc</surname>
</person_name>
</contributors>
<publication_date media_type='print'>
<year>2018</year>
</publication_date>
<pages>
<first_page>3</first_page>
<last_page>14</last_page>
</pages>
</journal_article>
</journal>
</body>
</doi_batch>