INVESTIGADORES
PONZONI Ignacio
congresos y reuniones científicas
Título:
Permutación de matrices ralas a una FTB inferior específica mediante descomposición de grafos
Autor/es:
PONZONI, IGNACIO; SÁNCHEZ, MABEL C.; BRIGNOLE, NÉLIDA B.
Lugar:
Buenos Aires
Reunión:
Simposio; XXVI JAIIO - WAIT 1997 (Primer Workshop Argentino de Informática Teórica); 1997
Institución organizadora:
Sociedad Argentina de Informática e Investigación Operativa (SADIO)
Resumen:
Se presenta un nuevo algoritmo de particionamiento para permutar matrices ralas a una forma triangular inferior en bloques (FTiB) específica para instrumentación. Se propone particionar la matriz de ocurrencia en dos etapas de descomposición basadas en teoría de grafos. La primera emplea el algoritmo de Hopcroft y Karp para efectuar el pareamiento de nodos, realizando la clasificación de vértices mediante una modificación del método de Dulmage y Mendelsohn propuesta por los autores. La segunda aplica el algoritmo de Tarjan a los bloques cuadrados obtenidos en la primera etapa.
