About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Algorithmica (New York)
Paper
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.