Result: Consecutive interval query and dynamic programming on intervals
Title:
Consecutive interval query and dynamic programming on intervals
Authors:
Source:
Discrete applied mathematics. 85(1):1-24
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 1998.
Publication Year:
1998
Physical Description:
print, 23 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Programmation mathématique, Mathematical programming, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Recherche information. Graphe, Information retrieval. Graph, Algorithme rapide, Fast algorithm, Algoritmo rápido, Clique graphe, Graph clique, Graphe intervalle, Interval graph, Grafo intervalo, Programmation dynamique, Dynamic programming, Programación dinámica, Structure donnée, Data structure, Estructura datos, Théorie graphe, Graph theory, Teoría grafo, Algorithme séquentiel, Sequential algorithm, Matrice Monge, Monge matrix
Document Type:
Academic journal
Article
File Description:
text
Language:
English
Author Affiliations:
IBM Research Division, T .J. Watson Res. Ctr., P.O. Box 218, Yorktown Heights, NY 10598, United States
IBM Research Division, Tokyo Res. Lab., 1623-14 Shimotsuruma, Yamato, Kanagawa, 242, Japan
IBM Research Division, Tokyo Res. Lab., 1623-14 Shimotsuruma, Yamato, Kanagawa, 242, Japan
ISSN:
0166-218X
Rights:
Copyright 1998 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Operational research. Management
Operational research. Management
Accession Number:
edscal.2299136
Database:
PASCAL Archive
Further Information
Given a set of points (nodes) on a line and a set of m weighted intervals defined on the nodes, we consider a particular dynamic programming (DP) problem on these intervals. If the weight function of the DP has convex or concave property, we can solve this DP problem efficiently by using matrix searching in Monge matrices, together with a new query data structure, which we call the consecutive query structure. We invoke our algorithm to obtain fast algorithms for sequential partition of a graph and for maximum K-clique of an interval graph.