Using GRASP for the cover by \(s\)-defective independent sets problem. (English) Zbl 1428.05096

Buchanan, Austin; Chen, Nannan; Ma, Xin

Butenko, Sergiy (ed.) et al., Examining robustness and vulnerability of networked systems. Selected papers of the NATO Advanced Research Workshop (ARW) on examining robustness and vulnerability of critical infrastructure networks, Kiev, Ukraine, June 3–5, 2013. Amsterdam: IOS Press. NATO Sci. Peace Secur. Ser. D, Inf. Commun. Secur. 37, 17-25 (2014).

An \(s\)-defective coloring of a graph \(G\) is a vertex coloring in which the subgraph induced by each color class has at most \(s\) edges. The case \(s=0\) is the usual proper vertex coloring. In this paper, a greedy construction and a local search procedure are provided for the \(s\)-defective coloring problem.
For the entire collection see [Zbl 1326.94006].

Reviewer: Amin Bahmanian (Normal)

MSC:

05C15	Coloring of graphs and hypergraphs
05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q25	Analysis of algorithms and problem complexity

Keywords:

chromatic number; defective coloring; greedy coloring; heuristic; GRASP