A FAST APPROXIMATION ALGORITHM FOR COMPUTING THE FREQUENCIES OF SUBGRAPHS IN A GIVEN GRAPH

被引：79

作者：

DUKE, RA

LEFMANN, H

RODL, V

机构：

[1] UNIV DORTMUND,FACHBEREICH INFORMAT,D-44221 DORTMUND,GERMANY

[2] UNIV IDAHO,DEPT MATH & STAT,MOSCOW,ID 83843

[3] EMORY UNIV,DEPT MATH & COMP SCI,ATLANTA,GA 30322

来源：

SIAM JOURNAL ON COMPUTING | 1995年 / 24卷 / 03期

关键词：

COUNTING SUBGRAPHS; REGULARITY LEMMA;

D O I：

10.1137/S0097539793247634

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we give an algorithm which, given a labeled graph on n vertices and a list of all labeled graphs on k vertices, provides for each graph H of this list an approximation to the number of induced copies of H in G with total error small. This algorithm has running time O(n(l/log) (log) (n), M(n)), where M(n) is the time needed to square an n by n matrix with 0, 1-entries over the integers. The main tool in designing this algorithm is a variant of the regularity lemma of Szemeredi.

引用

页码：598 / 620

页数：23

共 11 条

[1] THE ALGORITHMIC ASPECTS OF THE REGULARITY LEMMA [J].