The interval-merging problem

Research output: Contribution to journalArticle

Abstract

A closed interval is an ordered pair of real numbers [x, y], with x ≤ y. The interval [x, y] represents the set {i ∈ R{divides}x ≤ i ≤ y}. Given a set of closed intervals I = {[a1, b1], [a2, b2], ..., [ak, bk]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M (I) = {[x1, y1], [x2, y2], ..., [xj, yj]}, j ≤ k, such that the real numbers represented by I = {n-ary union}i = 1k [ai, bi] equal those represented by M (I) = {n-ary union}i = 1j [xi, yi]. In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.

Original languageEnglish
Pages (from-to)519-524
Number of pages6
JournalInformation sciences
Volume177
Issue number2
DOIs
Publication statusPublished - 2007 Jan 15

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'The interval-merging problem'. Together they form a unique fingerprint.

  • Cite this