Consecutive interval query and dynamic programming on intervals

Alok Aggarwal, Takeshi Tokuyama

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


Given a set of n points on a line and a set of m weighted intervals defined on these points, we consider a particular dynamic programming problem on these intervals. If the weights are all nonnegative or all nonpositive, we solve this dynamic programming problem efficiently by using matrix searching in Monge arrays, together with a new query data structure which we call the consecutive interval query structure. We invoke our algorithm to obtain fast algorithms for the sequential partition of a graph and for the partial clique covering of an interval graph.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings
EditorsKam Wing Ng, Prabhakar Raghavan, N.V. Balasubramanian, Francis Y.L. Chin
PublisherSpringer Verlag
Number of pages10
ISBN (Print)9783540575689
Publication statusPublished - 1993
Externally publishedYes
Event4th International Symposium on Algorithms and Computation, ISAAC 1993 - Hong Kong, China
Duration: 1993 Dec 151993 Dec 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume762 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Symposium on Algorithms and Computation, ISAAC 1993
CityHong Kong

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Consecutive interval query and dynamic programming on intervals'. Together they form a unique fingerprint.

Cite this