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...
Guardado en:
| Autores principales: | , |
|---|---|
| Lenguaje: | English |
| Publicado: |
Universidad Católica del Norte, Departamento de Matemáticas
2021
|
| Materias: | |
| 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!
|
| Sumario: | 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. |
|---|