|
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.
Received: 19.03.2007
Citation:
A. J. Perez Tchernov, R. I. Tyshkevich, “On the recognition algorithm of edge intersection graphs of linear $3$-uniform hypergraphs: prelarge cliques”, Tr. Inst. Mat., 15:2 (2007), 78–89
Linking options:
https://www.mathnet.ru/eng/timb100 https://www.mathnet.ru/eng/timb/v15/i2/p78
|
Statistics & downloads: |
Abstract page: | 244 | Full-text PDF : | 216 | References: | 36 |
|