### Finding a heaviest triangle is no harder than matrix multiplication

(2006) In Electronic Colloquium on Computational Complexity- 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(n2376). Our algorithm substantially

improves the previous time-bounds for this problem recently

established by Vassilevska et al. (STOC 2006, \O(n2688)) and

(ICALP 2006, \O(n2575)). Its asymptotic time complexity

matches that of the fastest known algorithm for finding \emph{a}

triangle (not necessarily a maximum-weight one) in a graph.

By... (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(n2376). Our algorithm substantially

improves the previous time-bounds for this problem recently

established by Vassilevska et al. (STOC 2006, \O(n2688)) and

(ICALP 2006, \O(n2575)). Its asymptotic time complexity

matches that of the fastest known algorithm for finding \emph{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 \emph{any} triangle in a graph with m edges, i.e., in time

\O(m141). (Less)

Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1671014

- author
- Czumaj, Artur
and Lingas, Andrzej
^{LU} - organization
- publishing date
- 2006
- type
- Book/Report
- publication status
- published
- subject
- in
- Electronic Colloquium on Computational Complexity
- pages
- 13 pages
- publisher
- [Publisher information missing]
- report number
- TR06-115
- ISSN
- 1433-8092
- project
- VR 2005-4085
- language
- English
- LU publication?
- yes
- id
- 5fe4baec-a88d-4263-8831-c507166a7f65 (old id 1671014)
- alternative location
- http://eccc.hpi-web.de/report/2006/115/
- date added to LUP
- 2016-04-04 09:18:08
- date last changed
- 2018-11-21 20:52:09

@techreport{5fe4baec-a88d-4263-8831-c507166a7f65, abstract = {{We show that for any 0, a maximum-weight triangle in an<br/><br> undirected graph with n vertices and real weights assigned to<br/><br> vertices can be found in time \O(n+n2+),<br/><br> where is the exponent of fastest matrix multiplication<br/><br> algorithm. By the currently best bound on , the running time<br/><br> of our algorithm is \O(n2376). Our algorithm substantially<br/><br> improves the previous time-bounds for this problem recently<br/><br> established by Vassilevska et al. (STOC 2006, \O(n2688)) and<br/><br> (ICALP 2006, \O(n2575)). Its asymptotic time complexity<br/><br> matches that of the fastest known algorithm for finding \emph{a}<br/><br> 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<br/><br> upper bounds on finding a maximum-weight triangle in a sparse graph<br/><br> and on finding a maximum-weight subgraph isomorphic to a fixed graph<br/><br> established in the papers by Vassilevska et al. For example, we can<br/><br> find a maximum-weight triangle in a vertex-weighted graph with m<br/><br> edges in asymptotic time required by the fastest algorithm for<br/><br> finding \emph{any} triangle in a graph with m edges, i.e., in time<br/><br> \O(m141).}}, author = {{Czumaj, Artur and Lingas, Andrzej}}, institution = {{[Publisher information missing]}}, issn = {{1433-8092}}, language = {{eng}}, number = {{TR06-115}}, series = {{Electronic Colloquium on Computational Complexity}}, title = {{Finding a heaviest triangle is no harder than matrix multiplication}}, url = {{http://eccc.hpi-web.de/report/2006/115/}}, year = {{2006}}, }