Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Fast distance multiplication of unit-Monge matrices

Tools
- Tools
+ Tools

Tiskin, Alexander (2015) Fast distance multiplication of unit-Monge matrices. Algorithmica, 71 (4). pp. 859-888. doi:10.1007/s00453-013-9830-z

Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/s00453-013-9830-z

Request Changes to record.

Abstract

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(n 2). 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(n 1.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(nlog2 n), 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.

Item Type: Journal Article
Divisions: Faculty of Science > Computer Science
Journal or Publication Title: Algorithmica
Publisher: Springer Verlag
ISSN: 0178-4617
Official Date: April 2015
Dates:
DateEvent
April 2015Published
19 September 2013Available
21 August 2013Accepted
3 November 2011Submitted
Volume: 71
Number: 4
Page Range: pp. 859-888
DOI: 10.1007/s00453-013-9830-z
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us