Dipartimento di Scienze Statistiche

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.