Sobre el problema de particionamiento de embalaje en grafos dirigidos
Autores: Samadi, Babak; Yero, Ismael G.
Idioma: Inglés
Editor: MDPI
Año: 2021
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
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.
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.