The Library
Finding a Heaviest Triangle is not Harder than Matrix Multiplication
Tools
Tools
Tools
Czumaj, Artur and Lingas, Andrzej (2007) Finding a Heaviest Triangle is not Harder than Matrix Multiplication. In: 18th ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, JAN 07-09, 2007. Published in: PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS pp. 986-994.
Full text not available from this repository.Abstract
We show that for any epsilon > 0, a maximum-weight triangle in an undirected graph with rt vertices and real weights assigned to vertices can be found in time O(n(omega) + n(2+epsilon)), where omega is the exponent of fastest matrix multiplication algorithm. By the currently best bound on omega, the running time of our algorithm is O(n(2.376)). Our algorithm substantially improves the previous time-bounds for this problem recently established by Vassilevska et al. (STOC 2006, O(n(2.688))) and (ICALP 2006, O(n(2.575))). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximum-weight one) in a graph. By applying or extending our algorithm, we can also improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph established in the papers by Vassilevska et al. For example, we can find a maximum-weight triangle in a vertexweighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with in edges, i.e., in time O(m(1.41)).
| Item Type: | Conference Item (UNSPECIFIED) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Computer Science |
| Journal or Publication Title: | PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS |
| Publisher: | SIAM |
| ISBN: | 978-0-898716-24-5 |
| Date: | 2007 |
| Number of Pages: | 9 |
| Page Range: | pp. 986-994 |
| Publication Status: | Published |
| Title of Event: | 18th ACM-SIAM Symposium on Discrete Algorithms |
| Location of Event: | New Orleans, LA |
| Date(s) of Event: | JAN 07-09, 2007 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/5150 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
