Permutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions

dc.creatorPonzoni, Ignacio
dc.creatorSánchez, Mabel C.
dc.creatorBrignole, Nélida B.
dc.date1998-06-26
dc.date2022-05-03T14:58:43Z
dc.date.accessioned2023-07-15T06:25:55Z
dc.date.available2023-07-15T06:25:55Z
dc.identifierhttp://sedici.unlp.edu.ar/handle/10915/135519
dc.identifierhttps://publicaciones.sadio.org.ar/index.php/EJS/article/view/136
dc.identifierissn:1514-6774
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/7476639
dc.descriptionA new partitioning algorithm that permutes sparse matrices to a specific block lower-triangular form (BlTF) complying with special features required for instrumentation problems is presented. The proposal consists in the decomposition of the occurrence matrix in two stages, using methodologies based on graph theory. First of all, Hopcroft-Karp´s algorithm is employed to match the vertices, this classification being carried out by means of a modification of Dulmage-Mendelsohn´s technique, which was devised by the authors. The second step is the application of Tarjan´s algorithm to the square blocks obtained as a result of the first stage.
dc.descriptionSociedad Argentina de Informática e Investigación Operativa
dc.formatapplication/pdf
dc.format76-87
dc.languageen
dc.rightshttp://creativecommons.org/licenses/by/4.0/
dc.rightsCreative Commons Attribution 4.0 International (CC BY 4.0)
dc.subjectCiencias Informáticas
dc.subjectGraph theory
dc.subjectdirected graphs
dc.subjectbipartite graphs
dc.subjectsparse matrices
dc.subjectblock lower-triangular forms
dc.subjectassignment algorithms
dc.subjectpartitioning algorithms
dc.titlePermutation of Sparse Matrices to a Specific Lower BTF using Graph Decompositions
dc.typeArticulo
dc.typeArticulo


Este ítem pertenece a la siguiente institución