Skip to main content
Springer Nature Link
Log in

Two-Way and Multiway Partitioning of a Set of Intervals for Clique-Width Maximization

  • Published:
Save article
View saved research
Algorithmica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from €37.37 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price includes VAT (Netherlands)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Author information

Authors and Affiliations

  1. IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA. ahf@watson.ibm.com., , , , , , US

    A. H. Farrahi

  2. Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208, USA. dtlee@ece.nwu.edu, majid@ece.nwu.edu., , , , , , US

    D.-T. Lee & M. Sarrafzadeh

Authors
  1. A. H. Farrahi
    View author publications

    Search author on:PubMed Google Scholar

  2. D.-T. Lee
    View author publications

    Search author on:PubMed Google Scholar

  3. M. Sarrafzadeh
    View author publications

    Search author on:PubMed Google Scholar

Additional information

Received May 27, 1997; revised October 30, 1997.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Farrahi, A., Lee, DT. & Sarrafzadeh, M. Two-Way and Multiway Partitioning of a Set of Intervals for Clique-Width Maximization . Algorithmica 23, 187–210 (1999). https://doi.org/10.1007/PL00009257

Download citation

  • Issue date:

  • DOI: https://doi.org/10.1007/PL00009257