Incompatibility graphs and data mining.
Endre Boros, Vincenzo Spinelli, Federica Ricca · Cologne Twente Workshop on Graphs and Combinatorial Optimization · 2011
In this paper, we investigate a new class of graphs, called “Incompatibility Graphs” which arise from Box Clustering. Besides their importance for the applications in data mining, these graphs have an intrinsic interest from a theoretical viewpoint, since they generalize some important classes of graphs, namely, chordal and weakly chordal graphs. The special structure of the Incompatibility Graphs can be exploited to efficiently solve some keyproblems related to Box Clustering, such as the “Maximum Box” and the “Minimum Covering by Boxes” problems. In fact, we show that these two problems can be formulated as a vertex packing and a vertex coloring one, respectively, in an Incompatibility Graph, and that one can solve in polynomial time the former and, for two important subclasses of instances, also the latter.