Tyck till om SwePub Sök
här!
Sökning: id:"swepub:oai:lup.lub.lu.se:33b04fb8-7727-4261-bba3-101a82d8404f" >
Finding a heaviest ...
Finding a heaviest triangle is not harder than matrix multiplication
-
Czumaj, Artur (författare)
-
- Lingas, Andrzej (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
(creator_code:org_t)
- 2007
- 2007
- Engelska.
-
Ingår i: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. - 9780898716245 ; , s. 986-994
- Relaterad länk:
-
http://portal.acm.or...
-
visa fler...
-
https://lup.lub.lu.s...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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).
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas