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
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
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)
Cited In (10)
- Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- Efficient approximation algorithms for shortest cycles in undirected graphs
- Elastic-Degenerate String Matching via Fast Matrix Multiplication
- Maximum-weight planar boxes in \(O(n^2)\) time (and better)
- Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs
- Hamming Distance Completeness
- Extreme witnesses and their applications
- All-pairs bottleneck paths in vertex weighted graphs
- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
- Title not available (Why is that?)
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)
