The Library
Finding a heaviest vertexweighted triangle is not harder than matrix multiplication
Tools
Czumaj, Artur and Lingas, Andrzej. (2009) Finding a heaviest vertexweighted triangle is not harder than matrix multiplication. SIAM Journal on Computing, Volume 39 (Number 2). pp. 431444. ISSN 00975397

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 maximumweight 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 timebounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximumweight one) in a graph. We can extend our algorithm to improve the upper bounds on finding a maximumweight triangle in a sparse graph and on finding a maximumweight subgraph isomorphic to a fixed graph. We can find a maximumweight triangle in a vertexweighted 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 maximumweight 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 > 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:  00975397  
Official Date:  2009  
Dates: 


Volume:  Volume 39  
Number:  Number 2  
Number of Pages:  14  
Page Range:  pp. 431444  
Identifier:  10.1137/070695149  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  National Science Foundation (U.S.) (NSF), Engineering and Physical Sciences Research Council (EPSRC), University of Warwick  
Grant number:  CCR0313219 (NSF), EP/D063191/1 (EPSRC), 62120054085 (VR)  
References:  [1] N. Alon, R. Yuster, and U. Zwick, Colorcoding, J. ACM, 42 (1995), pp. 844–856. 

URI:  http://wrap.warwick.ac.uk/id/eprint/17465 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year