Advanced

Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

Czumaj, Artur and Lingas, Andrzej LU (2009) In SIAM Journal on Computing 39(2). p.431-444
Abstract
We show that a maximum-weight 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 time-bounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximum-weight one) in a graph. We can extend our algorithm to 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. We can... (More)
We show that a maximum-weight 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 time-bounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximum-weight one) in a graph. We can extend our algorithm to 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. We can find a maximum-weight triangle in a vertex-weighted 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 maximum-weight 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:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
time complexity, graph algorithms, triangle, matrix multiplication, vertex-weighted graph, graph
in
SIAM Journal on Computing
volume
39
issue
2
pages
431 - 444
publisher
SIAM Publications
external identifiers
  • wos:000268859000005
  • scopus:67650112691
ISSN
0097-5397
DOI
10.1137/070695149
project
VR 2008-4649
language
English
LU publication?
yes
id
c71618dd-556b-4d9b-95a4-b6b5d6ff9b62 (old id 1477508)
date added to LUP
2009-09-22 15:27:08
date last changed
2017-09-03 04:07:54
@article{c71618dd-556b-4d9b-95a4-b6b5d6ff9b62,
  abstract     = {We show that a maximum-weight 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 time-bounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximum-weight one) in a graph. We can extend our algorithm to 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. We can find a maximum-weight triangle in a vertex-weighted 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 maximum-weight 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         = {0097-5397},
  keyword      = {time complexity,graph algorithms,triangle,matrix multiplication,vertex-weighted graph,graph},
  language     = {eng},
  number       = {2},
  pages        = {431--444},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Computing},
  title        = {Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication},
  url          = {http://dx.doi.org/10.1137/070695149},
  volume       = {39},
  year         = {2009},
}