zbMATH — the first resource for mathematics

Using GRASP for the cover by \(s\)-defective independent sets problem. (English) Zbl 1428.05096
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].
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
Full Text: Link