Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 1/2017

09.12.2016

On the Chromatic Number of Non-Sparse Random Intersection Graphs

verfasst von: Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis

Erschienen in: Theory of Computing Systems | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge when their label sets intersect. Random intersection graphs (RIGs) (as defined in Karoński et al. Comb. Probab. Comput. J. 8, 131–159 (1999); Singer-Cohen (1995)) consider label sets formed by the following experiment: each vertex, independently and uniformly, examines all the labels (m in total) one by one. Each examination is independent and the vertex succeeds to put the label in her set with probability p. Such graphs can capture interactions in networks due to sharing of resources among nodes. In this paper, we discuss various structural and algorithmic results concerning random intersection graphs and we focus on the computational problem of properly coloring random instances of the binomial random intersection graphs model. For the latter, we consider a range of parameters m, p for which RIGs differ substantially from Erdős-Rényi random graphs and for which greedy approaches fail.
Vorheriger Artikel Notes on Computable Analysis

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
Note however, that this does not mean that the chromatic number is close to np, since the part that is not coloured could be a clique in the worst case.
 
2
A perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Consequently, the clique number of a perfect graph is equal to its chromatic number.
 
3
More precisely, if \(\mathcal {B}\) is the set of different label choices that can give rise to a graph G, then the problem of inferring the complete information of label choices from G is solvable if there is some \(B^{*} \in \mathcal {B}\) such that Pr(B ∗|G) > Pr(B|G), for all \(\mathcal {B} \ni B \neq B^{*}\).
 
Literatur
1.
Leone, P., Moraru, L., Powell, O., Rolim, J.D.P.: Localization algorithm for wireless ad-hoc sensor networks with traffic overhead minimization by emission inhibition. In: Proceedings of the 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), pp 119–129 (2006)
2.
Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D., Wiese, A.: Communication in wireless networks with directional antennas. In: Proceedings of the 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp 344–351 (2008)
3.
Busch, C., Magdon-Ismail, M., Sivrikaya, F., Yener, B.: Contention-free MAC protocols for asynchronous wireless sensor networks. Distrib. Comput. 21(1), 23–42 (2008)CrossRefMATH
4.
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the 6th Annual ACM Symposium on Theory of Computing, pp. 47–63 (1974). doi:10.​1145/​800119.​803884
5.
6.
7.
8.
9.
Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.C.: Secure communication over radio channels. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp 105–114 (2008)
10.
Dolev, S., Lahiani, L., Yung, M.: Secret swarm unitreactive k-secret sharing. In: Proceedings of the 8th International Conference on Cryptology in India (INDOCRYPT), pp 123–137 (2007)
11.
Karoński, M., Sheinerman, E.R., Singer-Cohen, K.B.: On random intersection graphs: The subgraph problem. Comb. Probab. Comput. J. 8, 131–159 (1999)MathSciNetCrossRefMATH
12.
Singer-Cohen, K.B.: Random Intersection Graphs. PhD thesis, John Hopkins University (1995)
13.
Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Large independent sets in general random intersection graphs. Theor. Comput. Sci. 406, 215–224 (2008)MathSciNetCrossRefMATH
14.
Godehardt, E., Jaworski, J.: Two models of random intersection graphs for classification. In: Opitz, O., Schwaiger, M. (eds.) Studies in Classification, Data Analysis and Knowledge Organization, pp 67–82. Springer Verlag, Berlin, Heidelberg, New York (2002)
15.
Fill, J.A., Sheinerman, E.R., Singer-Cohen, K.B.: Random intersection graphs when m = ω(n): an equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models. Random Struct. Algoritm. 16(2), 156–176 (2000)MathSciNetCrossRefMATH
16.
17.
18.
19.
Behrisch, M., Taraz, A., Ueckerdt, M.: Coloring random intersection graphs and complex networks. SIAM J. Discrete Math. 23, 288–299 (2008)MathSciNetCrossRefMATH
20.
Nikoletseas, S., Raptopoulos, C., Spirakis, P.: Colouring non-sparse random intersection graphs. In: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp 600–611 (2009)
21.
22.
Ross, S.M.: Stochastic Processes, 2nd edn. Wiley (2000)
23.
Alon, N., Spencer, J.: The Probabilistic Method. Wiley (2000)
24.
Nikoletseas, S., Raptopoulos, C., Spirakis, P.: On the independence number and hamiltonicity of uniform random intersection graphs. In: Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp 1–11 (2009)
25.
26.
Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Springer (2002)
27.
Bloznelis, M., Godehardt, E., Jaworski, J., Kurauskas, V., Rybarczyk, K.: Recent progress in complex network analysis - models of random intersection graphs. In: Lausen, B., Krolak-Schwerdt, S., Bhmer, M. (eds.) Data Science, Learning by Latent Structures, and Knowledge Discovery, pp 59–68. Springer (2015)
28.
Raptopoulos, C., Spirakis, P.: Simple and efficient greedy algorithms for hamilton cycles in random intersection graphs (2005)
29.
Efthymiou, C., Spirakis, P.G.: Sharp thresholds for Hamiltonicity in random intersection graphs. Theor. Comput. Sci. 411(40–42), 3714–3730 (2010)MathSciNetCrossRefMATH
30.
Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Maximum cliques in graphs with small intersection number and random intersection graphs. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp 728–739 (2012)
31.
Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Expander properties and the cover time of random intersection graphs. Theor. Comput. Sci. 410(50), 5261–5272 (2009)MathSciNetCrossRefMATH
32.
Cooper, C., Frieze, A.: The cover time of sparse random graphs. In: Random Structures and Algorithms, vol. 30, pp 1–16. Wiley (2007)
Metadaten
Titel
On the Chromatic Number of Non-Sparse Random Intersection Graphs
verfasst von
Sotiris E. Nikoletseas
Christoforos L. Raptopoulos
Paul G. Spirakis
Publikationsdatum
09.12.2016
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 1/2017
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-016-9733-x

Weitere Artikel der Ausgabe 1/2017

Theory of Computing Systems 1/2017 Zur Ausgabe

EditorialNotes

50 Years of TOCS

OriginalPaper

Local Restrictions from the Furst-Saxe-Sipser Paper

OriginalPaper

Notes on Computable Analysis

OriginalPaper

Arithmetic for Rooted Trees

OriginalPaper

Incremental Problems in the Parameterized Complexity Setting