К проблеме распознавания реберных графов линейных $3$-униформных гиперграфов: предбольшие клики

Известно, что проблема распознавания класса $L^l_k$ — графов пересечений ребер линейных $k$-униформных гиперграфов — является $NP$-полной для $k\ge 3$. Известна схема алгоритма, решающего задачу распознавания $G\in L^l_3$ для графов с минимальной степенью вершин $\delta(G)\ge 10$ за время $O(n+m)$, где $n$ — порядок (число вершин), а $m$ — размер (число ребер) тестируемого графа $G$. В работе предлагается модификация этого алгоритма, ориентированная на практические применения.
Библиогр. 14 назв.