论文标题
在大图中认证诱导的子图
Certifying Induced Subgraphs in Large Graphs
论文作者
论文摘要
我们介绍了I/O-Oftimal认证算法，用于二分图，以及分裂，阈值，两部分链和琐碎的完美图的类别。当输入图是类成员时，认证算法将返回以此类为特征的证书。否则，它将返回禁止的诱导子图作为非会员的证书。在带有$ n $顶点和$ m $边缘的图表上，我们的算法在最坏情况下或具有双部分链图的最佳$ o（\ text {stort {stort}（n + m））$ i/os $ i/os，并且证书以最佳i/os返回证书。我们提供了拆分和阈值图的实现，并提供了实验评估。
We introduce I/O-optimal certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a class member, the certifying algorithm returns a certificate that characterizes this class. Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership. On a graph with $n$ vertices and $m$ edges, our algorithms take optimal $O(\text{sort}(n + m))$ I/Os in the worst case or with high probability for bipartite chain graphs, and the certificates are returned in optimal I/Os. We give implementations for split and threshold graphs and provide an experimental evaluation.
