Tyck till om SwePub Sök
här!
Sökning: id:"swepub:oai:lup.lub.lu.se:5fe4baec-a88d-4263-8831-c507166a7f65" >
Finding a heaviest ...
Finding a heaviest triangle is no 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)
- 2006
- Engelska 13 s.
-
Serie: Electronic Colloquium on Computational Complexity, 1433-8092 ; TR06-115
- Relaterad länk:
-
http://eccc.hpi-web.... (free)
-
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(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).
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- rap (ämneskategori)
- vet (ämneskategori)