solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看7727次
Finding induced subgraphs in scale-free inhomogeneous random graphs. (arXiv:1801.08293v1 [cs.DS])
来源于:arXiv
We study the induced subgraph isomorphism problem on inhomogeneous random
graphs with infinite variance power-law degrees. We provide a fast algorithm
that determines for any connected graph $H$ on $k$ vertices if it exists as
induced subgraph in a random graph with $n$ vertices. By exploiting the
scale-free graph structure, the algorithm runs in $O(n e^{k^4})$ time, and
finds for constant $k$ an instance of $H$ in linear time with high probability. 查看全文>>