Finding a heaviest triangle is not harder than matrix multiplication
(2007) Symposium on Discrete Algorithms, 2007 p.986994 Abstract
 We show that for any ε > 0, a maximumweight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(nω + n2+ε), where ω is the exponent of fastest matrix multiplication algorithm. By the currently best bound on ω, the running time of our algorithm is O(n2.376). Our algorithm substantially improves the previous timebounds for this problem recently established by Vassilevska et al. (STOC 2006, O(n2.688)) and (ICALP 2006, O(n2.575)). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximumweight one) in a graph.
By applying or extending our algorithm, we can also improve the upper bounds on finding... (More)  We show that for any ε > 0, a maximumweight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(nω + n2+ε), where ω is the exponent of fastest matrix multiplication algorithm. By the currently best bound on ω, the running time of our algorithm is O(n2.376). Our algorithm substantially improves the previous timebounds for this problem recently established by Vassilevska et al. (STOC 2006, O(n2.688)) and (ICALP 2006, O(n2.575)). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximumweight one) in a graph.
By applying or extending our algorithm, we can also improve the upper bounds on finding a maximumweight triangle in a sparse graph and on finding a maximumweight subgraph isomorphic to a fixed graph established in the papers by Vassilevska et al. For example, we can find a maximumweight triangle in a vertexweighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time O(m1.41). (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/629534
 author
 Czumaj, Artur and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2007
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 host publication
 Proceedings of the eighteenth annual ACMSIAM symposium on Discrete algorithms
 pages
 986  994
 publisher
 Society for Industrial and Applied Mathematics
 conference name
 Symposium on Discrete Algorithms, 2007
 conference location
 New Orleans, Louisiana, United States
 conference dates
 20070107  20070109
 external identifiers

 scopus:84969247244
 ISBN
 9780898716245
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 33b04fb877274261bba3101a82d8404f (old id 629534)
 alternative location
 http://portal.acm.org/citation.cfm?id=1283489
 date added to LUP
 20071127 15:06:11
 date last changed
 20190106 11:40:42
@inproceedings{33b04fb877274261bba3101a82d8404f, abstract = {We show that for any ε > 0, a maximumweight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(nω + n2+ε), where ω is the exponent of fastest matrix multiplication algorithm. By the currently best bound on ω, the running time of our algorithm is O(n2.376). Our algorithm substantially improves the previous timebounds for this problem recently established by Vassilevska et al. (STOC 2006, O(n2.688)) and (ICALP 2006, O(n2.575)). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximumweight one) in a graph.<br/><br> <br/><br> By applying or extending our algorithm, we can also improve the upper bounds on finding a maximumweight triangle in a sparse graph and on finding a maximumweight subgraph isomorphic to a fixed graph established in the papers by Vassilevska et al. For example, we can find a maximumweight triangle in a vertexweighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time O(m1.41).}, author = {Czumaj, Artur and Lingas, Andrzej}, isbn = {9780898716245}, language = {eng}, location = {New Orleans, Louisiana, United States}, pages = {986994}, publisher = {Society for Industrial and Applied Mathematics}, title = {Finding a heaviest triangle is not harder than matrix multiplication}, year = {2007}, }