Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Finding Small Complete Subgraphs Efficiently
Ke Chen, Adrian Dumitrescu, Andrzej Lingas
(I) We revisit the algorithmic problem of finding all triangles in a graph with vertices and edges. According to a result of Chiba and Nishizeki (1985), this task…
cs.DS2024
Finding Triangles or Independent Sets; and Other Dual Pair Approximations
Adrian Dumitrescu
We revisit the algorithmic problem of finding a triangle in a graph (\textsc{Triangle Detection}), and examine its relation to other problems such as \textsc{3Sum}, \textsc{Indepen…