
doi: 10.1007/pl00021184
A hypergraph \(H=(V,\{X_i \mid i\in I\})\) is \(k\)-uniform if all hyperedges \(X_i\) have the same cardinality \(k\); it is \(k\)-conformal if there is some graph \(G\) such that \(H\) is isomorphic to the hypergraph of all cliques with \(k\) vertices of \(G\). The intersection multigraph of \(H\) has \(\{x_i \mid i\in I\}\) as vertex set, and two distinct vertices \(x_i\), \(x_j\) are joined by \(| X_i\cap X_j| \) parallel edges. While the recognition problem of intersection multigraphs of \(k\)--uniform hypergraphs \((k\geq 3)\) is NP-complete, the author shows that intersection multigraphs of 3-uniform, 3-conformal hypergraphs can be recognized and the (essentially unique) root hypergraph can be reconstructed in polynomial time. Intersection multigraphs of \(k\)-uniform, \(k\)-conformal hypergraphs \((k\geq 4)\) with one additional property are also discussed.
recognition algorithm, intersection multigraphs, Graph algorithms (graph-theoretic aspects), cliques, Hypergraphs, uniform hypergraphs
recognition algorithm, intersection multigraphs, Graph algorithms (graph-theoretic aspects), cliques, Hypergraphs, uniform hypergraphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
