nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

A Hybrid Approach for Exact Coloring of Massive Graphs

verfasst von : Emmanuel Hebrard, George Katsirelos

Erschienen in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The graph coloring problem appears in numerous applications, yet many state-of-the-art methods are hardly applicable to real world, very large, networks. The most efficient approaches for massive graphs rely on “peeling” the graph of its low-degree vertices and focus on the maximum k-core where k is some lower bound on the chromatic number of the graph. However, unless the graphs are extremely sparse, the cores can be very large, and lower and upper bounds are often obtained using greedy heuristics.

In this paper, we introduce a combined approach using local search to find good quality solutions on massive graphs as well as locate small subgraphs with potentially large chromatic number. The subgraphs can be used to compute good lower bounds, which makes it possible to solve optimally extremely large graphs, even when they have large k-cores.

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 "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

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

Vorheriges Kapitel Repairing Learned Controllers with Convex Optimization: A Case Study

Nächstes Kapitel Modelling and Solving the Minimum Shift Design Problem

http://www.info.univ-angers.fr/~porumbel/graphs/.

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-19212-9_25/478365_1_En_25_IEq127_HTML.gif

denotes our implementation of the Dsatur heuristic.

Ties broken by overall degree.

Sources available at: https://bitbucket.org/gkatsi/minicsp.

Sources available at: https://bitbucket.org/gkatsi/gc-cdcl/src/master/.

Personnal communication with the authors.

email-Eu-core, email-EuAll, Gnutella08/09, bitcoinalpha, bitcoinotc, facebook, gplus, CollegeMsg and sx-superuser.

Aardal, K.I., Hoesel, S.P.M.V., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Ann. Oper. Res. 153(1), 79–129 (2007)MathSciNetCrossRef

Abello, J., Pardalos, P., Resende, M.G.C.: On maximum clique problems in very large graphs. In: Abello, J.M., Vitter, J.S. (eds.) External Memory Algorithms, pp. 119–130. American Mathematical Society, Boston (1999)CrossRef

Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D.: Graph partitioning and graph clustering (2012). http://www.cc.gatech.edu/dimacs10/

Blöchliger, I., Zufferey, N.: A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35(3), 960–975 (2008)MathSciNetCrossRef

Brélaz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979)MathSciNetCrossRef

Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Comput. Lang. 6(1), 47–57 (1981)CrossRef

Cornaz, D., Jost, V.: A one-to-one correspondence between colorings and stable sets. Oper. Res. Lett. 36(6), 673–676 (2008)MathSciNetCrossRef

de Werra, D.: An introduction to timetabling. Eur. J. Oper. Res. 19(2), 151–162 (1985)MathSciNetCrossRef

Furini, F., Gabrel, V., Ternier, I.-C.: Lower bounding techniques for DSATUR-based branch and bound. Electron. Notes Discrete Math. 52, 149–156 (2016). INOC 2015–7th International Network Optimization ConferenceMathSciNetCrossRef

10.

Hao, J.-K., Qinghua, W.: Improving the extraction and expansion method for large graph coloring. Discrete Appl. Math. 160(16–17), 2397–2407 (2012)MathSciNetCrossRef

11.

Hebrard, E., Katsirelos, G.: Clause learning and new bounds for graph coloring. In: Hooker, J. (ed.) CP 2018. LNCS, vol. 11008, pp. 179–194. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98334-9_12CrossRef

12.

Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. Computing 39(4), 345–351 (1987)MathSciNetCrossRef

13.

Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11–13, 1993. American Mathematical Society, Boston (1996)MATH

14.

Leighton, F.T.: A graph coloring algorithm for large scheduling problems. J. Res. Natl. Bur. Stand. 84, 489–506 (1979)MathSciNetCrossRef

15.

Leskovec, J., Krevl, A.: SNAP datasets: Stanford large network dataset collection (2014). http://snap.stanford.edu/data

16.

Lin, J., Cai, S., Luo, C., Su, K.: A reduction based method for coloring very large graphs. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 517–523 (2017)

17.

Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theor. 25(1), 1–7 (2006)MathSciNetCrossRef

18.

Malaguti, E., Monaci, M., Toth, P.: An exact approach for the vertex coloring problem. Discrete Optim. 8(2), 174–190 (2011)MathSciNetCrossRef

19.

Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417–427 (1983)MathSciNetCrossRef

20.

Mehrotra, A., Trick, M.A.: A column generation approach for graph coloring. INFORMS J. Comput. 8, 344–354 (1995)CrossRef

21.

Moalic, L., Gondran, A.: Variations on memetic algorithms for graph coloring problems. CoRR, abs/1401.2184 (2014)

22.

Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161–162 (1955)MathSciNetCrossRef

23.

Park, T., Lee, C.Y.: Application of the graph coloring algorithm to the frequency assignment problem. J. Oper. Res. Soc. Jpn. 39(2), 258–265 (1996)MathSciNetCrossRef

24.

Rossi, R.A., Ahmed, N.K.: Coloring large complex networks. CoRR, abs/1403.3448 (2014)

25.

Schaafsma, B., Heule, M.J.H., van Maaren, H.: Dynamic symmetry breaking by simulating zykov contraction. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 223–236. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02777-2_22CrossRef

26.

Segundo, P.S.: A new DSATUR-based algorithm for exact vertex coloring. Comput. Oper. Res. 39(7), 1724–1733 (2012)MathSciNetCrossRef

27.

Van Gelder, A.: Another look at graph coloring via propositional satisfiability. Discrete Appl. Math. 156(2), 230–243 (2008)MathSciNetCrossRef

28.

Verma, A., Buchanan, A., Butenko, S.: Solving the maximum clique and vertex coloring problems on very large sparse networks. INFORMS J. Comput. 27(1), 164–177 (2015)CrossRef

29.

Walteros, J.L., Buchanan, A.: Why is maximum clique often easy in practice? Optimization Online (2018). http://www.optimization-online.org/DB_HTML/2018/07/6710.html

30.

Zhou, Z., Li, C.-M., Huang, C., Ruchu, X.: An exact algorithm with learning for the graph coloring problem. Comput. Oper. Res. 51, 282–301 (2014)MathSciNetCrossRef

Titel: A Hybrid Approach for Exact Coloring of Massive Graphs
verfasst von: Emmanuel Hebrard
George Katsirelos
Verlag: Springer International Publishing
Buch: Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Print ISBN: 978-3-030-19211-2

Electronic ISBN: 978-3-030-19212-9

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-19212-9_25

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner