Finding a heaviest vertexweighted triangle is not harder than matrix multiplication
(2009) In SIAM Journal on Computing 39(2). p.431444 Abstract
 We show that a maximumweight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(n(omega) + n(2+o(1))), where omega is the exponent of the 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 timebounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximumweight one) in a graph. We can extend our algorithm to improve the upper bounds on finding a maximumweight triangle in a sparse graph and on finding a maximumweight subgraph isomorphic to a fixed graph. We can... (More)
 We show that a maximumweight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(n(omega) + n(2+o(1))), where omega is the exponent of the 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 timebounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximumweight one) in a graph. We can extend our algorithm to improve the upper bounds on finding a maximumweight triangle in a sparse graph and on finding a maximumweight subgraph isomorphic to a fixed graph. 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(m(1.41)). Our algorithms for a maximumweight fixed subgraph (in particular any clique of constant size) are asymptotically as fast as the fastest known algorithms for a fixed subgraph. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1477508
 author
 Czumaj, Artur and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2009
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 time complexity, graph algorithms, triangle, matrix multiplication, vertexweighted graph, graph
 in
 SIAM Journal on Computing
 volume
 39
 issue
 2
 pages
 431  444
 publisher
 Society for Industrial and Applied Mathematics
 external identifiers

 wos:000268859000005
 scopus:67650112691
 ISSN
 00975397
 DOI
 10.1137/070695149
 project
 VR 20084649
 language
 English
 LU publication?
 yes
 id
 c71618dd556b4d9b95a4b6b5d6ff9b62 (old id 1477508)
 date added to LUP
 20160401 13:34:50
 date last changed
 20210922 03:35:40
@article{c71618dd556b4d9b95a4b6b5d6ff9b62, abstract = {We show that a maximumweight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(n(omega) + n(2+o(1))), where omega is the exponent of the 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 timebounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximumweight one) in a graph. We can extend our algorithm to improve the upper bounds on finding a maximumweight triangle in a sparse graph and on finding a maximumweight subgraph isomorphic to a fixed graph. 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(m(1.41)). Our algorithms for a maximumweight fixed subgraph (in particular any clique of constant size) are asymptotically as fast as the fastest known algorithms for a fixed subgraph.}, author = {Czumaj, Artur and Lingas, Andrzej}, issn = {00975397}, language = {eng}, number = {2}, pages = {431444}, publisher = {Society for Industrial and Applied Mathematics}, series = {SIAM Journal on Computing}, title = {Finding a heaviest vertexweighted triangle is not harder than matrix multiplication}, url = {http://dx.doi.org/10.1137/070695149}, doi = {10.1137/070695149}, volume = {39}, year = {2009}, }