RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2007 Volume 15, Number 2, Pages 78–89 (Mi timb100)

On the recognition algorithm of edge intersection graphs of linear $3$-uniform hypergraphs: prelarge cliques

A. J. Perez Tchernov, R. I. Tyshkevich

Belarusian State University

Abstract: Let $L^l_k$ be the class of edge intersection graphs of linear $k$-uniform hypergraphs. It is known that the recognition problem "$G\in L^l_k$" is $NP$-complete for $k\ge 3$, but there exists an algorithm deciding whether $G\in L^l_3$ for graphs $G$ with minimal vertex degree $\delta(G)\ge 10$. In this paper we provide the practical oriented modification of this algorithm.

UDC: 519.1

Received: 19.03.2007



© Steklov Math. Inst. of RAS, 2024