Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Finding a heaviest triangle is not harder than matrix multiplication

Czumaj, Artur and Lingas, Andrzej LU (2007) Symposium on Discrete Algorithms, 2007 p.986-994
Abstract
We show that for any ε > 0, a maximum-weight 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 time-bounds 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 maximum-weight 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 maximum-weight 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 time-bounds 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 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 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(m1.41). (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the eighteenth annual ACM-SIAM 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
2007-01-07 - 2007-01-09
external identifiers
  • scopus:84969247244
ISBN
978-0-898716-24-5
project
VR 2005-4085
language
English
LU publication?
yes
id
33b04fb8-7727-4261-bba3-101a82d8404f (old id 629534)
alternative location
http://portal.acm.org/citation.cfm?id=1283489
date added to LUP
2016-04-04 11:00:12
date last changed
2022-02-21 04:01:10
@inproceedings{33b04fb8-7727-4261-bba3-101a82d8404f,
  abstract     = {{We show that for any ε &gt; 0, a maximum-weight 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 time-bounds 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 maximum-weight one) in a graph.<br/><br>
<br/><br>
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 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(m1.41).}},
  author       = {{Czumaj, Artur and Lingas, Andrzej}},
  booktitle    = {{Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms}},
  isbn         = {{978-0-898716-24-5}},
  language     = {{eng}},
  pages        = {{986--994}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  title        = {{Finding a heaviest triangle is not harder than matrix multiplication}},
  url          = {{http://portal.acm.org/citation.cfm?id=1283489}},
  year         = {{2007}},
}