Finding the largest triangle in a graph in expected quadratic time

DOI10.1016/J.EJOR.2020.03.059MaRDI QIDQ2184135zbMATH OpenOpenAlexFDO

Authors Giuseppe Lancia, Paolo Vidoni

Publication date 27 May 2020

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2020.03.059

zbMATH Keywords

3-OPT TSP neighborhoodapplied probabilitycombinatorial optimizationmax weight triangleprobabilistic analysis of algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Finding a heaviest triangle is not harder than matrix multiplication
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Listing triangles
• Finding heaviest H-subgraphs in real weighted graphs, with applications

Cites work

• Fine-grained complexity analysis of two classic TSP variants
• scientific article; zbMATH DE number 3863589 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• Introduction to algorithms.
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Order Statistics
• Subcubic equivalences between path, matrix, and triangle problems
• Traveling salesman problem heuristics: leading methods, implementations and latest advances
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(4)

• Algebraic Bayesian networks: checking backbone connectivity
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• Finding a heaviest triangle is not harder than matrix multiplication
• Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Finding the largest triangle in a graph in expected quadratic time

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