Show simple item record

A linear time algorithm for minimum equitable dominating set in trees

dc.creatorRana, Sohel
dc.creatorNayeem, Sk. Md. Abu
dc.date2021-07-25
dc.date.accessioned2023-09-22T12:43:09Z
dc.date.available2023-09-22T12:43:09Z
dc.identifierhttps://www.revistaproyecciones.cl/index.php/proyecciones/article/view/4552
dc.identifier10.22199/issn.0717-6279-4552
dc.identifier.urihttps://revistaschilenas.uchile.cl/handle/2250/234441
dc.descriptionLet G = (V, E) be a graph. A subset De of V is said to be an equitable dominating set if for every v ∈ V \ De there exists u ∈ De such that uv ∈ E and |deg(u) − deg(v)| ≤ 1, where, deg(u) and deg(v) denote the degree of the vertices u and v respectively. An equitable dominating set with minimum cardinality is called the minimum equitable dominating set and its cardinality is called the equitable domination number and it is denoted by γe. The problem of finding minimum equitable dominating set in general graphs is NP-complete. In this paper, we give a linear time algorithm to determine minimum equitable dominating set of a tree.en-US
dc.formatapplication/pdf
dc.languageeng
dc.publisherUniversidad Católica del Norte.en-US
dc.relationhttps://www.revistaproyecciones.cl/index.php/proyecciones/article/view/4552/3830
dc.rightsCopyright (c) 2021 Sohel Rana, Sk. Md. Abu Nayeemen-US
dc.rightshttp://creativecommons.org/licenses/by/4.0en-US
dc.sourceProyecciones (Antofagasta, On line); Vol. 40 No. 4 (2021); 805-814en-US
dc.sourceProyecciones. Revista de Matemática; Vol. 40 Núm. 4 (2021); 805-814es-ES
dc.source0717-6279
dc.source10.22199/issn.0717-6279-2021-04
dc.subjectEquitable dominationen-US
dc.subjectLinear time algorithmen-US
dc.subjectTreesen-US
dc.subject05C05en-US
dc.subject05C69en-US
dc.subject05C85en-US
dc.titleA linear time algorithm for minimum equitable dominating set in treesen-US
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion
dc.typetexten-US


This item appears in the following Collection(s)

Show simple item record