|
Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity
Yu. Metelsky, R. Shatsov Belarusian State University, Minsk
Abstract:
Let $L^m_k$ denote the class of edge intersection graphs of hypergraphs with rank at most $k$ and multiplicity at most $m.$ It is proved that the problem of recognizing graphs of the class $L^m_k$ is NP-complete for fixed $k \ge 3,$ $m \ge 1.$
Received: 26.09.2016
Citation:
Yu. Metelsky, R. Shatsov, “Complexity of recognizing edge intersection graphsof hypergraphs with bounded above rank and multiplicity”, Tr. Inst. Mat., 24:2 (2016), 98–105
Linking options:
https://www.mathnet.ru/eng/timb316 https://www.mathnet.ru/eng/timb/v24/i2/p98
|
|