A linear time algorithm for minimum equitable dominating set in trees

Abstract Let G = (V, E) be a graph. A subset D e of V is said to be an equitable dominating set if for every v ∈ V \ D e there exists u ∈ D e such that uv ∈ E and |deg(u) − deg(v)| ≤ 1, where, deg(u) and deg(v) denote the degree of the vertices u...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Rana,Sohel, Nayeem,Sk. Md. Abu
Lenguaje:	English
Publicado:	Universidad Católica del Norte, Departamento de Matemáticas 2021
Materias:	Equitable domination Linear time algorithm Trees
Acceso en línea:	http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0716-09172021000400805
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:scielo:S0716-09172021000400805
record_format	dspace
spelling	oai:scielo:S0716-091720210004008052021-08-12A linear time algorithm for minimum equitable dominating set in treesRana,SohelNayeem,Sk. Md. Abu Equitable domination Linear time algorithm Trees Abstract Let G = (V, E) be a graph. A subset D e of V is said to be an equitable dominating set if for every v ∈ V \ D e there exists u ∈ D e 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.info:eu-repo/semantics/openAccessUniversidad Católica del Norte, Departamento de MatemáticasProyecciones (Antofagasta) v.40 n.4 20212021-01-01text/htmlhttp://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0716-09172021000400805en10.22199/issn.0717-6279-4552
institution	Scielo Chile
collection	Scielo Chile
language	English
topic	Equitable domination Linear time algorithm Trees
spellingShingle	Equitable domination Linear time algorithm Trees Rana,Sohel Nayeem,Sk. Md. Abu A linear time algorithm for minimum equitable dominating set in trees
description	Abstract Let G = (V, E) be a graph. A subset D e of V is said to be an equitable dominating set if for every v ∈ V \ D e there exists u ∈ D e 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.
author	Rana,Sohel Nayeem,Sk. Md. Abu
author_facet	Rana,Sohel Nayeem,Sk. Md. Abu
author_sort	Rana,Sohel
title	A linear time algorithm for minimum equitable dominating set in trees
title_short	A linear time algorithm for minimum equitable dominating set in trees
title_full	A linear time algorithm for minimum equitable dominating set in trees
title_fullStr	A linear time algorithm for minimum equitable dominating set in trees
title_full_unstemmed	A linear time algorithm for minimum equitable dominating set in trees
title_sort	linear time algorithm for minimum equitable dominating set in trees
publisher	Universidad Católica del Norte, Departamento de Matemáticas
publishDate	2021
url	http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0716-09172021000400805
work_keys_str_mv	AT ranasohel alineartimealgorithmforminimumequitabledominatingsetintrees AT nayeemskmdabu alineartimealgorithmforminimumequitabledominatingsetintrees AT ranasohel lineartimealgorithmforminimumequitabledominatingsetintrees AT nayeemskmdabu lineartimealgorithmforminimumequitabledominatingsetintrees
_version_	1718439907591979008

A linear time algorithm for minimum equitable dominating set in trees

Ejemplares similares