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}}, }