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, Los Angeles, 07-09 Jan 2007. Published in: Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms pp. 986-994. ISBN 9780898716245.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 (Paper) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Journal or Publication Title: | Proceeding SODA '07 Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms |
| Publisher: | Society for Industrial and Applied Mathematics |
| ISBN: | 9780898716245 |
| Official Date: | 2007 |
| Dates: | Date Event 2007 Published |
| Number of Pages: | 9 |
| Page Range: | pp. 986-994 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Conference Paper Type: | Paper |
| Title of Event: | 18th ACM-SIAM Symposium on Discrete Algorithms |
| Type of Event: | Other |
| Location of Event: | New Orleans, Los Angeles |
| Date(s) of Event: | 07-09 Jan 2007 |
| URI: | https://wrap.warwick.ac.uk/5150/ |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |