logo móvil
Contáctanos

Total dominación romana {3}: la complejidad y algoritmo de tiempo lineal para árboles

Autores: Liu, Xinyue; Jiang, Huiqin; Wu, Pu; Shao, Zehui

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

Acceso abierto

Artículo científico
2021

Total dominación romana {3}: la complejidad y algoritmo de tiempo lineal para árboles


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Grafo simple
Vértices aislados
Función de dominación total Romana {3}
Peso
Número de dominación total Romana {3}
NP-completo
Grafos planares
Grafos bipartitos cordales
Algoritmo de tiempo lineal
árboles

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 31

Citaciones: Sin citaciones


Descripción
Para un grafo simple sin vértices aislados, una función total de dominación Romana {3} (TR3DF) en es una función que tiene la propiedad de que (i) si ; (ii) si ; y (iii) cada vértice con tiene un vecino con para cada vértice . El peso de un TR3DF es la suma y el peso mínimo de una función total de dominación Romana {3} en se llama el número total de dominación Romana {3} denotado por . En este artículo, mostramos que el problema de dominación total Romana {3} es NP-completo para grafos planares y grafos bipartitos cordales. Finalmente, presentamos un algoritmo de tiempo lineal para calcular el valor de para árboles.

Otros recursos que podrían interesarte

Temas Virtualpro