Two-Way and Multiway Partitioning of a Set of Intervals for Clique-Width Maximization |
| |
| Authors: | A H Farrahi D-T Lee M Sarrafzadeh |
| |
| Affiliation: | (1) IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA. ahf@watson.ibm.com., US;(2) Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208, USA. dtlee@ece.nwu.edu, majid@ece.nwu.edu., US |
| |
| Abstract: | For a set S of intervals, the clique-interva
I
S
is defined as the interval obtained from the intersection of all the intervals in S , and the clique-width quantity w
S
is defined as the length of I
S
. 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(k n
2
) time algorithm for the k -way unbalanced partitioning problem.
Received May 27, 1997; revised October 30, 1997. |
| |
| Keywords: | , Interval graphs, Partitioning, Clique-width, Sleep mode, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
