Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MAXIMUM WEIGHT SUBGRAPH:
Reports tagged with maximum weight subgraph:
TR06-115 | 26th July 2006
Artur Czumaj, Andrzej Lingas

#### Finding a Heaviest Triangle is not Harder than Matrix Multiplication

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 ... more >>>

ISSN 1433-8092 | Imprint