Finding a heaviest triangle is not harder than matrix multiplication
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.Full text not available from this repository.
Official URL: http://dl.acm.org/citation.cfm?id=1283489
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 > 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|
|Number of Pages:||9|
|Page Range:||pp. 986-994|
|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|
Actions (login required)