logo móvil
Contáctanos

Sobre el problema de particionamiento de embalaje en grafos dirigidos

Autores: Samadi, Babak; Yero, Ismael G.

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

Acceso abierto

Artículo científico
2021

Sobre el problema de particionamiento de embalaje en grafos dirigidos


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Empaquetando conjuntos
Dígrafos
Particionamiento
Conjunto de vértices
Cardinalidad
árboles dirigidos

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 29

Citaciones: Sin citaciones


Descripción
Este trabajo tiene como objetivo continuar estudiando los conjuntos de empaquetamiento de digrafos a través de la perspectiva de particionar el conjunto de vértices de un digrafo en conjuntos de empaquetamiento (que pueden interpretarse como un tipo de coloración de vértices de digrafos) y se enfoca en encontrar la cardinalidad mínima entre todas las particiones de empaquetamiento para un digrafo dado, llamado el número de partición de empaquetamiento de . Se demuestran algunos límites inferiores y superiores sobre este parámetro, y se presentan sus valores exactos para árboles dirigidos en este artículo. En el caso de árboles dirigidos, la prueba resulta en un algoritmo de tiempo polinómico para encontrar una partición de empaquetamiento de cardinalidad mínima. También consideramos este parámetro en productos de digrafos. En particular, se presenta una solución completa para este caso al tratar con los productos enraizados.

Otros recursos que podrían interesarte

Temas Virtualpro