Efficient transitive closure of sparse matrices over closed semirings

DOI10.1016/J.TCS.2005.11.008MaRDI QIDQ2368941zbMATH OpenOpenAlexFDO

Authors Gerald Penn

Publication date 28 April 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.11.008

zbMATH Keywords

Dijkstra's algorithmParsingSemiringsSparse matrix multiplicationTyped feature logic

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Data structures (68P05) Natural language processing (68T50) Symbolic computation and algebraic computation (68W30)

Recommendations

• Efficient computation of transitive closures
• A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices
• scientific article; zbMATH DE number 88951
• Fast multiplication of matrices over a finitely generated semiring
• The transitive closure and the reduction of nilpotent matrices over an additively idempotent semiring
• On minimum matrix representation of closure operations
• Matrix sparsification and nested dissection over arbitrary fields
• scientific article; zbMATH DE number 827923
• Closure, commutativity and minimal complexity of some spaces of matrices
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs

Cites work

• A heuristic improvement of the Bellman-Ford algorithm
• A note on two problems in connexion with graphs
• A Theorem on Boolean Matrices
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 487935 (Why is no real title available?)
• scientific article; zbMATH DE number 1175490 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• New Bounds on the Complexity of the Shortest Path Problem
• On practical algorithms for accelerated matrix multiplication
• Shortest paths algorithms: Theory and experimental evaluation
• The algebraic structure of transitive closure and its application to attribute type signatures

Cited in

(8)

• A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices
• On minimum matrix representation of closure operations
• Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures
• ViennaCL-linear algebra library for multi- and many-core architectures
• Memory-Efficient Sparse Matrix-Matrix Multiplication by Row Merging on Many-Core Architectures
• The algebraic structure of transitive closure and its application to attribute type signatures
• Evaluating regular path queries on compressed adjacency matrices
• Mantaining dynamic matrices for fully dynamic transitive closure

Describes a project that uses

Uses Software

• Algorithm 97
• WordNet
• DIMACS

This page was built for publication: Efficient transitive closure of sparse matrices over closed semirings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368941)