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
Mathematics in Computer Science
Erschienen in: Mathematics in Computer Science 1/2020

20.09.2019

Vertex Coloring of a Graph for Memory Constrained Scenarios

verfasst von: Eduardo Sant’Ana da Silva, Helio Pedrini

Erschienen in: Mathematics in Computer Science | Ausgabe 1/2020

Einloggen

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

search-config
loading …

Abstract

Given an undirected graph \(G=(V,E)\), where V is a set of n vertices and E is a set of m edges, the vertex coloring problem consists in assigning colors to the graph vertices such that no two adjacent vertices share the same color. The vertex coloring problem has several practical applications, for instance, resource scheduling, compiler register allocation, pattern matching, puzzle solving, exam timetabling, among others. It is known that the problem of vertex k-coloring of a graph, for any \(k \ge 3\), is NP-complete. In this work, we focus on an approximate solution that can be implemented on simple electronic equipments that do not require a complete set of operations present in common microprocessors. The solution is suitable for sensors and other devices present in several applications for collecting and measuring data.
Vorheriger Artikel On Meandric Colliers
Nächster Artikel Modular Techniques for Noncommutative Gröbner Bases

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
Literatur
1.
2.
Arumugam, S., Premalatha, K., Bača, M., Semaničová-Feňovčíková, A.: Local antimagic vertex coloring of a graph. Gr. Comb. 33(2), 275–285 (2017)MathSciNetMATHCrossRef
3.
Barba, L., Cardinal, J., Korman, M., Langerman, S., Van Renssen, A., Roeloffzen, M., Verdonschot, S.: Dynamic graph coloring. In: Workshop on Algorithms and Data Structures, pp. 97–108. Springer (2017)
4.
Beigel, R., Eppstein, D.: 3-Coloring in time \(0(1.3446^n)\): a no-MIS algorithm. In: 36th Annual Symposium on Foundations of Computer Science, pp. 444–452. IEEE (1995)
5.
Bhattacharya, S., Chakrabarty, D., Henzinger, M., Nanongkai, D.: Dynamic algorithms for graph coloring. In: 29th Annual ACM-SIAM symposium on discrete algorithms, pp. 1–20. Society for Industrial and Applied Mathematics (2018)
6.
Bollobás, B.: Modern Graph Theory. Graduate Texts in Mathematics. Springer, Berlin (1998)MATHCrossRef
7.
Boman, E.G., Bozdağ, D., Catalyurek, U., Gebremedhin, A.H., Manne, F.: A scalable parallel graph coloring algorithm for distributed memory computers. In: European Conference on Parallel Processing, pp. 241–251. Springer (2005)
8.
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. The Macmillan Press Ltd. (1976)
9.
Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Stein, M., Zhong, M.: Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica 38(4), 779–801 (2018)MathSciNetMATHCrossRef
10.
11.
Burjons, E., Hromkovič, J., Královič, R., Královič, R., Muñoz, X., Unger, W.: Online graph coloring against a randomized adversary. Int. J. Found. Comput. Sci. 29(04), 551–569 (2018)MathSciNetMATHCrossRef
12.
Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32(6), 547–556 (2004)MathSciNetMATHCrossRef
13.
Chen, L., Peng, J., Ralescu, D.A.: Uncertain vertex coloring problem. Soft Comput. 23(4), 1337–1346 (2019)MATHCrossRef
14.
Coleman, T.F., Moré, J.J.: Estimation of sparse Jacobian matrices and graph coloring blems. SIAM J. Numer. Anal. 20(1), 187–209 (1983)MathSciNetMATHCrossRef
15.
Dao, H.T., Kim, S.: Vertex graph-coloring-based pilot assignment with location-based channel estimation for massive MIMO systems. IEEE Access 6, 4599–4607 (2018)CrossRef
16.
Dharwadker, A.: A new proof of the four colour theorem. Can. Math. Soc. 221, 1–34 (2000)
17.
Diks, K.: A fast parallel algorithm for six-colouring of planar graphs. In: International Symposium on Mathematical Foundations of Computer Science, pp. 273–282. Springer (1986)
18.
Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 329–337. Society for Industrial and Applied Mathematics (2001)
19.
Eppstein, D.: Small maximal independent sets and faster exact graph coloring. In: Workshop on Algorithms and Data Structures, pp. 462–470. Springer (2001)
20.
Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H. Freeman and Company, New York (2002)
21.
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: 6th Annual ACM Symposium on Theory of Computing, pp. 47–63. ACM (1974)
22.
23.
Grech, N., Kastrinis, G., Smaragdakis, Y.: Efficient reflection string analysis via graph coloring. In: 32nd European Conference on Object-Oriented Programming, p. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)
24.
Grötzsch, H.: Zur Theorie der Diskreten Gebilde. VII. Ein Dreifarbensatz far Dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe 8, 109–120 (1958/1959)
25.
26.
27.
Janczewski, R., Kubale, M., Manuszewski, K., Piwakowski, K.: The smallest hard-to-color graph for algorithm DSATUR. Discret. Math. 236(1), 151–165 (2001)MathSciNetMATHCrossRef
28.
29.
30.
31.
32.
van Lint, J., Wilson, R.: A Course in Combinatorics. Cambridge University Press, Cambridge (2001)MATHCrossRef
33.
34.
35.
36.
Moalic, L., Gondran, A.: Variations on memetic algorithms for graph coloring problems. J. Heurist. 24(1), 1–24 (2018)CrossRef
37.
Mustafa, H., Schilken, I., Karasikov, M., Eickhoff, C., Rätsch, G., Kahles, A.: Dynamic compression schemes for graph coloring. Bioinformatics 35(3), 407–414 (2018)CrossRef
38.
39.
40.
Orden, D., Gimenez-Guzman, J., Marsa-Maestre, I., de la Hoz, E.: Spectrum graph coloring and applications to Wi-Fi channel assignment. Symmetry 10(3), 65 (2018)MATHCrossRef
41.
42.
Ramsey, F.: On a problem of formal logic. In: Classic Papers in Combinatorics, pp. 1–24. Springer (2009)
43.
44.
Şeker, O., Ekim, T., Taşkın, Z.C.: A decomposition approach to solve the selective graph coloring problem in some perfect graph families. Networks 73(2), 145–169 (2019)MathSciNetCrossRef
45.
Silva, E., Guedes, A., Todt, E.: Independent spanning trees on systems-on-chip hypercubes routing. Int. Conf. Electron. Circuits Syst. 75, 93–96 (2013)
46.
47.
Welsh, D.J., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J. 10(1), 85–86 (1967)MATHCrossRef
48.
Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization, pp. 185–207. Springer (2003)
49.
Zhou, Y., Duval, B., Hao, J.K.: Improving probability learning based local search for graph coloring. Appl. Soft Comput. 65, 542–553 (2018)CrossRef
Metadaten
Titel
Vertex Coloring of a Graph for Memory Constrained Scenarios
verfasst von
Eduardo Sant’Ana da Silva
Helio Pedrini
Publikationsdatum
20.09.2019
Verlag
Springer International Publishing
Erschienen in
Mathematics in Computer Science / Ausgabe 1/2020
Print ISSN: 1661-8270
Elektronische ISSN: 1661-8289
DOI
https://doi.org/10.1007/s11786-019-00409-4

Weitere Artikel der Ausgabe 1/2020

Mathematics in Computer Science 1/2020 Zur Ausgabe

OriginalPaper

Exploring the Isoptics of Fermat Curves in the Affine Plane Using DGS and CAS

OriginalPaper

On Meandric Colliers

OriginalPaper

Computing Coupled Border Bases

OriginalPaper

Nori Diagrams and Persistent Homology

OriginalPaper

On the Extension of Adams–Bashforth–Moulton Methods for Numerical Integration of Delay Differential Equations and Application to the Moon’s Orbit

OriginalPaper

The Depth of Compositions

Premium Partner

    Bildnachweise