Fast distance multiplication of unit-Monge matrices
From MaRDI portal
Publication:2350900
DOI10.1007/S00453-013-9830-ZzbMath1325.68259DBLPjournals/algorithmica/Tiskin15OpenAlexW3137678020WikidataQ59410201 ScholiaQ59410201MaRDI QIDQ2350900
Publication date: 25 June 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9830-z
Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Approximation algorithms (68W25) Numerical linear algebra (65F99)
Related Items (11)
Finding a Maximum Clique in a Grounded 1-Bend String Graph ⋮ A substring-substring LCS data structure ⋮ Demazure product of permutations and hopping ⋮ Unnamed Item ⋮ A Scalable Approximation Algorithm for Weighted Longest Common Subsequence ⋮ Unnamed Item ⋮ A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation ⋮ Unnamed Item ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Fast and longest rollercoasters ⋮ A data structure for substring-substring LCS length queries
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the representation theory of finite \(J\)-trivial monoids
- Approximately matching context-free languages
- Faster subsequence recognition in compressed strings
- On the longest increasing subsequence of a circular list
- Representation and classification of Coxeter monoids
- The Bruhat order on symmetric varieties
- Semi-local string comparison: algorithmic techniques and applications
- Let sleeping files lie: Pattern matching in Z-compressed files.
- TP\(_2\) = Bruhat
- Semi-local longest common subsequences in subquadratic time
- Geometric applications of a matrix-searching algorithm
- A faster algorithm computing string edit distances
- Additive complexity in directed computations
- New clique and independent set algorithms for circle graphs
- Statistical properties of locally free groups with applications to braid groups and growth of random heaps
- Noncommutative Schur functions and their applications
- Double Catalan monoids
- On line arrangements in the hyperbolic plane
- Application of max-plus algebra to biological sequence comparisons
- Two new criteria for comparison in the Bruhat order
- Algorithmic graph theory and perfect graphs
- A subquadratic algorithm for approximate limited expression matching
- Perspectives of Monge properties in optimization
- Unified compression-based acceleration of edit-distance computation
- Fast and compact regular expression matching
- Graphs, dioids and semirings. New models and algorithms.
- Stable Grothendieck polynomials and \(K\)-theoretic factor sequences
- Algorithmics on SLP-compressed strings: A survey
- Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition
- Combinatorics of Coxeter Groups
- All Semi-local Longest Common Subsequences in Subquadratic Time
- Efficient algorithms for finding maximum cliques of an overlap graph
- Efficient Parallel Algorithms for String Editing and Related Problems
- Processing Compressed Texts: A Tractability Border
- How often are two permutations comparable?
- More algorithms for all-pairs shortest paths in weighted graphs
- Max-linear Systems: Theory and Algorithms
- Periodic String Comparison
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- Finding maximum cliques in circle graphs
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Algorithms on Strings, Trees and Sequences
- The String-to-String Correction Problem
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Braid Groups
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Querying and Embedding Compressed Texts
This page was built for publication: Fast distance multiplication of unit-Monge matrices
