Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

Artur Czumaj, Andrzej Lingas

    Research output: Contribution to journalArticlepeer-review

    13 Citations (SciVal)

    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.
    Original languageEnglish
    Pages (from-to)431-444
    JournalSIAM Journal on Computing
    Volume39
    Issue number2
    DOIs
    Publication statusPublished - 2009

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • time complexity
    • graph algorithms
    • triangle
    • matrix multiplication
    • vertex-weighted graph
    • graph

    Fingerprint

    Dive into the research topics of 'Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication'. Together they form a unique fingerprint.

    Cite this