Czumaj, Artur and Lingas, A.. (2009) Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication. SIAM Journal on Computing (SICOMP), 39 (2). pp. 431-444. ISSN 0097-5397

Full text not available from this repository.

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 $\mathcal{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 $\mathcal{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 $\mathcal{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 > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	SIAM Journal on Computing (SICOMP)
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0097-5397
Date:	2009
Volume:	39
Number:	2
Page Range:	pp. 431-444
Identification Number:	10.1137/070695149
Publication Status:	Published
Related URLs:	Other Repository
URI:	http://wrap.warwick.ac.uk/id/eprint/47506

Request changes to a record

Actions (login required)

View Item