The Library
Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
Tools
Czumaj, Artur and Lingas, Andrzej (2009) Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM Journal on Computing, Volume 39 (Number 2). pp. 431-444. doi:10.1137/070695149 ISSN 0097-5397.
|
PDF
WRAP_Czumaj_GetPDFServlet2.pdf - Published Version - Requires a PDF viewer. Download (388Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/070695149
Abstract
We show that a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(n(omega) + n(2+o(1))), where omega is the exponent of the fastest matrix multiplication algorithm. By the currently best bound on omega, the running time of our algorithm is O(n(2.376)). Our algorithm substantially improves the previous time-bounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximum-weight one) in a graph. We can extend our algorithm to 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. 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(m(1.41)). Our algorithms for a maximum-weight fixed subgraph (in particular any clique of constant size) are asymptotically as fast as the fastest known algorithms for a fixed subgraph.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Graph algorithms, Triangle, Matrices | ||||
Journal or Publication Title: | SIAM Journal on Computing | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 2009 | ||||
Dates: |
|
||||
Volume: | Volume 39 | ||||
Number: | Number 2 | ||||
Number of Pages: | 14 | ||||
Page Range: | pp. 431-444 | ||||
DOI: | 10.1137/070695149 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 8 December 2015 | ||||
Date of first compliant Open Access: | 8 December 2015 | ||||
Funder: | National Science Foundation (U.S.) (NSF), Engineering and Physical Sciences Research Council (EPSRC), University of Warwick | ||||
Grant number: | CCR-0313219 (NSF), EP/D063191/1 (EPSRC), 621-2005-4085 (VR) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year