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
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
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.
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.