Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication

DOI10.1137/070695149zbMath1200.68123OpenAlexW2018033449MaRDI QIDQ3558009

Andrzej Lingas, Artur Czumaj

Publication date: 29 April 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/17465/1/WRAP_Czumaj_GetPDFServlet2.pdf

zbMATH Keywords

graph algorithmstime complexitymatrix multiplicationvertex-weighted graphgraph triangle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Extreme Witnesses and Their Applications ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ On minimum witnesses for Boolean matrix multiplication ⋮ Detecting and Counting Small Pattern Graphs ⋮ Unnamed Item ⋮ Extreme witnesses and their applications ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication

This page was built for publication: Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication