Finding a maximum weight triangle in n 3-Δ time, with applications

DOI10.1145/1132516.1132550zbMath1301.05342OpenAlexW2057393374MaRDI QIDQ2931387

R. Ryan Williams, Virginia Vassilevska Williams

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132550

zbMATH Keywords

triangleindependent setcliquematrix multiplicationdominating pairssub-cubic algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20) Signed and weighted graphs (05C22)

Related Items (8)

All-pairs bottleneck paths in vertex weighted graphs ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Unnamed Item ⋮ Extreme witnesses and their applications ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Hamming Distance Completeness ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication

This page was built for publication: Finding a maximum weight triangle in n ^3-Δ time, with applications