COLORING RANDOM INTERSECTION GRAPHS AND COMPLEX NETWORKS

被引：14

作者：

Behrisch, Michael ^{[1
]}

Taraz, Anusch ^{[2
]}

Ueckerdt, Michael ^{[1
]}

机构：

[1] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

[2] Tech Univ Munich, Zentrum Math, D-80290 Munich, Germany

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2009年 / 23卷 / 01期

关键词：

coloring; intersection graph; random graph; complex network;

D O I：

10.1137/050647153

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the evolution of the chromatic number of a random intersection graph and show that, in a certain range of parameters, these random graphs can be colored optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.

引用

页码：288 / 299

页数：12

共 18 条

[1]

ALBERT R., DATABASE SELF ORG NE

[2] Efficiently covering complex networks with cliques of similar vertices [J].

Behrisch, M ;

Taraz, A .

THEORETICAL COMPUTER SCIENCE, 2006, 355 (01) :37-47

[3]

BEHRISCH M., 2007, ELECTRON J COMB, V14, P12

[4]

Diestel R., 1997, Graph Theory

[5]

Fill JA, 2000, RANDOM STRUCT ALGOR, V16, P156, DOI 10.1002/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO

[6]

2-H

[7] Accelerating screening of 3D protein data with a graph theoretical approach [J].

Frömmel, C ;

Gille, C ;

Goede, A ;

Gröpl, C ;

Hougardy, S ;

Nierhoff, T ;

Preissner, R ;

Thimm, M .

BIOINFORMATICS, 2003, 19 (18) :2442-2447

[8]

GODEHARDT E., 2001, ELECT NOTES DISCRETE, V10

[9]

GOVINDAN R., 1999, SCAN LUCENT INTERNET

[10] Bipartite structure of all complex networks [J].

Guillaume, JL ;

Latapy, M .

INFORMATION PROCESSING LETTERS, 2004, 90 (05) :215-221

← 1 2 →