Artículo

Complexity of solving a system of difference constraints with variables restricted to a finite set

Cifuentes, SantiagoIcon ; Soulignac, Francisco JuanIcon ; Terlisky, Pablo Ezequiel
Fecha de publicación: 08/2023
Editorial: Elsevier Science
Revista: Information Processing Letters
ISSN: 0020-0190
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

Fishburn developed an algorithm to solve a system of m difference constraints whose n unknowns must take values from a set with k real numbers (Fishburn, 2002 [2]). We provide an implementation of Fishburn's algorithm that runs in O(n+km) time.
Palabras clave: DESIGN OF ALGORITHMS , SYSTEM OF DIFFERENCE CONSTRAINTS , VALUES IN A FINITE SET
 
Archivos asociados
Tamaño: 201.7Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/restrictedAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/218753
URL: https://linkinghub.elsevier.com/retrieve/pii/S0020019023000212
DOI: http://dx.doi.org/10.1016/j.ipl.2023.106378
Colecciones
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Citación
Cifuentes, Santiago; Soulignac, Francisco Juan; Terlisky, Pablo Ezequiel; Complexity of solving a system of difference constraints with variables restricted to a finite set; Elsevier Science; Information Processing Letters; 182; 8-2023; 1-3
Compartir
Altmétricas