TY - JOUR

T1 - Fast Distance Multiplication of Unit-Monge Matrices

AU - Tiskin, Alexander

PY - 2015/4/1

Y1 - 2015/4/1

N2 - Monge matrices play a fundamental role in optimisation theory, graph and string algorithms. Distance multiplication of two Monge matrices of size n can be performed in time O(n2). Motivated by applications to string algorithms, we introduced in previous works a subclass of Monge matrices, that we call simple unit-Monge matrices. We also gave a distance multiplication algorithm for such matrices, running in time O(n1.5). Landau asked whether this problem can be solved in linear time. In the current work, we give an algorithm running in time O(nlogn), thus approaching an answer to Landau’s question within a logarithmic factor. The new algorithm implies immediate improvements in running time for a number of algorithms on strings and graphs. In particular, we obtain an algorithm for finding a maximum clique in a circle graph in time O(nlog2n), and a surprisingly efficient algorithm for comparing compressed strings. We also point to potential applications in group theory, by making a connection between unit-Monge matrices and Coxeter monoids. We conclude that unit-Monge matrices are a fascinating object and a powerful tool, that deserve further study from both the mathematical and the algorithmic viewpoints.

AB - Monge matrices play a fundamental role in optimisation theory, graph and string algorithms. Distance multiplication of two Monge matrices of size n can be performed in time O(n2). Motivated by applications to string algorithms, we introduced in previous works a subclass of Monge matrices, that we call simple unit-Monge matrices. We also gave a distance multiplication algorithm for such matrices, running in time O(n1.5). Landau asked whether this problem can be solved in linear time. In the current work, we give an algorithm running in time O(nlogn), thus approaching an answer to Landau’s question within a logarithmic factor. The new algorithm implies immediate improvements in running time for a number of algorithms on strings and graphs. In particular, we obtain an algorithm for finding a maximum clique in a circle graph in time O(nlog2n), and a surprisingly efficient algorithm for comparing compressed strings. We also point to potential applications in group theory, by making a connection between unit-Monge matrices and Coxeter monoids. We conclude that unit-Monge matrices are a fascinating object and a powerful tool, that deserve further study from both the mathematical and the algorithmic viewpoints.

KW - 0-Hecke monoid

KW - Circle graphs

KW - Seaweed braids

KW - String comparison

KW - Unit-Monge matrices

UR - http://www.scopus.com/inward/record.url?scp=84924851334&partnerID=8YFLogxK

U2 - 10.1007/s00453-013-9830-z

DO - 10.1007/s00453-013-9830-z

M3 - Article

AN - SCOPUS:84924851334

VL - 71

SP - 859

EP - 888

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -