logo móvil
Contáctanos

El ancho de claque de los digrafos mínimos en serie-paralelo

Autores: Gurski, Frank; Quaddoura, Ruzayn

Idioma: Inglés

Editor: MDPI

Año: 2025

Descargar PDF

Acceso abierto

Artículo científico
2025

El ancho de claque de los digrafos mínimos en serie-paralelo


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Mínimo
Digrafos serie-paralelo
Ancho de clique dirigido
Cota superior
árbol de descomposición binaria
Consecuencias algorítmicas

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 38

Citaciones: Sin citaciones


Descripción
Los DAG de MSP (abreviatura de digrafos mínimos serie-paralelo) se pueden definir a partir del grafo de un solo vértice aplicando la composición en paralelo y la composición en serie. Demostramos un límite superior de 6 para el ancho de clique dirigido de los DAG de MSP y mostramos cómo se puede encontrar en tiempo lineal una expresión de ancho de clique dirigido 6. Nuestra expresión 6 se puede usar para construir un DAG de MSP a partir de su árbol de descomposición binaria en tiempo lineal. Aplicamos nuestro límite en el ancho de clique dirigido para concluir una serie de consecuencias algorítmicas para los DAG de MSP.

Otros recursos que podrían interesarte

Temas Virtualpro