Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
From MaRDI portal
Publication:4633908
zbMATH Open1423.68575MaRDI QIDQ4633908FDOQ4633908
Authors: Raphael Yuster 
Publication date: 6 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=1496873
Recommendations
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- Fast algorithms for the dominating set problem on permutation graphs
- Faster all-pairs shortest paths via circuit complexity
- scientific article; zbMATH DE number 219247
Permutations, words, matrices (05A05) Randomized algorithms (68W20) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38)
Cited In (12)
- A fast algorithm for multiplying min-sum permutations
- Efficient parameterized algorithms for computing all-pairs shortest paths
- Dominance product and high-dimensional closest pair under \(L_\infty\)
- Fast matrix multiplication and its algebraic neighbourhood
- Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
- \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
- Hamming Distance Completeness
- Twin-width. III: Max independent set, min dominating set, and coloring
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- Brief announcement: Hamming distance completeness and sparse matrix multiplication
- Remarks on ‘equivalence of stability concepts for discrete time-varying systems’
- Design and Analysis of a Tree-Backtracking Algorithm for Multiset and Pure Permutations
This page was built for publication: Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4633908)
