The Library
Finding a heaviest triangle is not harder than matrix multiplication
Tools
Czumaj, Artur and Lingas, Andrzej (2007) Finding a heaviest triangle is not harder than matrix multiplication. In: 18th ACMSIAM Symposium on Discrete Algorithms, New Orleans, Los Angeles, 0709 Jan 2007. Published in: Proceeding SODA '07 Proceedings of the eighteenth annual ACMSIAM symposium on Discrete algorithms pp. 986994. ISBN 9780898716245.
Research output not available from this repository, contact author.
Official URL: http://dl.acm.org/citation.cfm?id=1283489
Abstract
We show that for any epsilon > 0, a maximumweight triangle in an undirected graph with rt vertices and real weights assigned to vertices can be found in time O(n(omega) + n(2+epsilon)), where omega is the exponent of 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 recently established by Vassilevska et al. (STOC 2006, O(n(2.688))) and (ICALP 2006, O(n(2.575))). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximumweight one) in a graph.
By applying or extending our algorithm, we can also improve the upper bounds on finding a maximumweight triangle in a sparse graph and on finding a maximumweight subgraph isomorphic to a fixed graph established in the papers by Vassilevska et al. For example, 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 in edges, i.e., in time O(m(1.41)).
Item Type:  Conference Item (Paper)  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics 

Divisions:  Faculty of Science > Computer Science  
Journal or Publication Title:  Proceeding SODA '07 Proceedings of the eighteenth annual ACMSIAM symposium on Discrete algorithms  
Publisher:  Society for Industrial and Applied Mathematics  
ISBN:  9780898716245  
Official Date:  2007  
Dates: 


Number of Pages:  9  
Page Range:  pp. 986994  
Status:  Peer Reviewed  
Publication Status:  Published  
Conference Paper Type:  Paper  
Title of Event:  18th ACMSIAM Symposium on Discrete Algorithms  
Type of Event:  Other  
Location of Event:  New Orleans, Los Angeles  
Date(s) of Event:  0709 Jan 2007 
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 