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

DOI10.1145/1132516.1132550zbMATH Open1301.05342OpenAlexW2057393374MaRDI QIDQ2931387FDOQ2931387

Authors Virginia Vassilevska Williams, Ryan 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

trianglecliqueindependent setmatrix multiplicationdominating pairssub-cubic algorithm

Mathematics Subject Classification ID

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

Recommendations

• Finding the largest triangle in a graph in expected quadratic time
• A linear-time approximation scheme for maximum weight triangulation of convex polygons
• An almost four-approximation algorithm for maximum weight triangulation
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• A quasi-polynomial time approximation scheme for minimum weight triangulation
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Polynomial-time instances of the minimum weight triangulation problem
• Approximating minimum-weight triangulations in three dimensions
• Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound
• New results for the minimum weight triangulation problem

Cited in

(14)

• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Losing weight by gaining edges
• Finding the largest triangle in a graph in expected quadratic time
• Improved time bounds for all pairs non-decreasing paths in general digraphs
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Maximum-weight planar boxes in \(O(n^2)\) time (and better)
• Extreme witnesses and their applications
• Finding a heaviest triangle is not harder than matrix multiplication
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Hamming Distance Completeness
• All-pairs bottleneck paths in vertex weighted graphs
• Even faster 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931387)