Recognizing random intersection graphs

DOI10.1016/S0012-365X(00)00018-2MaRDI QIDQ1587611zbMATH OpenFDO

Authors Erich Prisner

Publication date 9 November 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(00)00018-2

zbMATH Keywords

intersection graphsrandom graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Review text

For a hypergraph \(H=(V,E)\) the \(l\)-intersection graph \(\Omega_l(H)\) has the vertex set \(E\) and two of its vertices are adjacent if the corresponding edges of \(H\) have at least \(l\) common elements. The author designs a polynomial-time algorithm that reconstructs a simple \(k\)-uniform hypergraph from its \(l\)-intersection graph for a class of random \(k\)-uniform hypergraphs. He also presents two algorithms for reconstructing almost every random graph from its related hypergraphs.

Recommendations

• Publication:4729111
• The intersection graph of random sets
• A guided tour in random intersection graphs
• Random intersection graphs with communities
• Selected Combinatorial Properties of Random Intersection Graphs
• Recognizing intersection graphs of linear uniform hypergraphs
• On Some Combinatorial Properties of Random Intersection Graphs
• On Random Intersection Graphs: The Subgraph Problem

Cited in

(4)

• Intersection multigraphs of uniform hypergraphs
• Shotgun assembly of Erdős-Rényi random graphs
• Isomorphism for random \(k\)-uniform hypergraphs
• Recognition of overlap graphs

This page was built for publication: Recognizing random intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1587611)