On random intersection graphs: The subgraph problem

被引：135

作者：

Karonski, M ^{[1
]}

Scheinerman, ER

Singer-Cohen, KB

机构：

[1] Adam Mickiewicz Univ, Fac Math & Comp Sci, Poznan, Poland

[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA

[3] Johns Hopkins Univ, Dept Math Sci, Baltimore, MD 21218 USA

[4] Univ Minnesota, Sch Math, Minneapolis, MN 55455 USA

来源：

COMBINATORICS PROBABILITY & COMPUTING | 1999年 / 8卷 / 1-2期

关键词：

D O I：

10.1017/S0963548398003459

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A new model of random graphs - random intersection graphs - is introduced. In this model, vertices are assigned random subsets of a given set. Two vertices are adjacent provided their assigned sets intersect. We explore the evolution of random intersection graphs by studying thresholds for the appearance and disappearance of small induced subgraphs. An application to gate matrix circuit design is presented.

引用

页码：131 / 159

页数：29

共 19 条

[1]

[Anonymous], 1985, SURVEYS COMBINATORIC

[2]

[Anonymous], 1960, MAGYAR TUD AKAD MAT

[3]

Bollobas B, 1985, RANDOM GRAPHS

[4]

DAS S, 1989, LECT NOTES COMPUTER, V405, P280

[5]

DAS S, EXPECTED NUMBER TRAC

[6] EXACT AND APPROXIMATE SOLUTIONS FOR THE GATE MATRIX LAYOUT PROBLEM [J].

DEO, N ;

KRISHNAMOORTHY, MS ;

LANGSTON, MA .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (01) :79-84

[7] NONCONSTRUCTIVE ADVANCES IN POLYNOMIAL-TIME COMPLEXITY [J].

FELLOWS, MR ;

LANGSTON, MA .

INFORMATION PROCESSING LETTERS, 1987, 26 (03) :157-162

[8] ON SEARCH, DECISION, AND THE EFFICIENCY OF POLYNOMIAL-TIME ALGORITHMS [J].

FELLOWS, MR ;

LANGSTON, MA .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 49 (03) :769-779

[9]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[10]

KARONSKI M, 1995, HDB COMBINATORICS, V1, P351

← 1 2 →