We show that for any $\epsilon > 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^{\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 time-bounds 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 \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(m^{1.41})$.