Two-way and multiway partitioning of a set of intervals for clique-width maximization

Abstract

For a set S of intervals, the clique-interval IS is defined as the interval obtained from the intersection of all the intervals in S, and the clique-width quantity wS is defined as the length of IS. Given a set S of intervals, it is straightforward to compute its clique-interval and clique-width. In this paper we study the problem of partitioning a set of intervals in order to maximize the sum of the clique-widths of the partitions. We present an O(n log n) time algorithm for the balanced bipartitioning problem, and an O(kn2) time algorithm for the k-way unbalanced partitioning problem.