Finding the largest triangle in a graph in expected quadratic time
| Autor: | Giuseppe Lancia, Paolo Vidoni |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Combinatorial optimization
Information Systems and Management General Computer Science 0211 other engineering and technologies Applied probability 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Max weight triangle Combinatorics Quadratic equation 0502 economics and business Probabilistic analysis of algorithms Time complexity Mathematics 3-OPT TSP neighborhood 050210 logistics & transportation 021103 operations research Conjecture Euclidean space 05 social sciences Graph Modeling and Simulation MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | European Journal of Operational Research. 286:458-467 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2020.03.059 |
| Popis: | Finding the largest triangle in an n-nodes edge-weighted graph belongs to a set of problems all equivalent under subcubic reductions. Namely, a truly subcubic algorithm for any one of them would imply that they are all subcubic. A recent strong conjecture states that none of them can be solved in less than Θ(n3) time, but this negative result does not rule out the possibility of algorithms with average, rather than worst-case, subcubic running time. Indeed, in this work we describe the first truly-subcubic average complexity procedure for this problem for graphs whose edge lengths are uniformly distributed in [0,1]. Our procedure finds the largest triangle in average quadratic time, which is the best possible complexity of any algorithm for this problem. We also give empirical evidence that the quadratic average complexity holds for many other random distributions of the edge lengths. A notable exception is when the lengths are distances between random points in Euclidean space, for which the algorithm takes average cubic time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect