A Hybrid Approach for Exact Coloring of Massive Graphs

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.
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.laas.fr/hal-02076298
Contributor : Emmanuel Hebrard <>
Submitted on : Friday, March 22, 2019 - 9:29:21 AM
Last modification on : Wednesday, July 3, 2019 - 4:50:08 PM
Long-term archiving on : Sunday, June 23, 2019 - 1:00:35 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02076298, version 1

Citation

Emmanuel Hébrard, George Katsirelos. A Hybrid Approach for Exact Coloring of Massive Graphs. Sixteenth International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2019), Jun 2019, Thessaloniki, Greece. ⟨hal-02076298⟩

Share

Metrics

Record views

51

Files downloads

63