Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Sparsity Preserving Algorithms for Octagons

MPG-Autoren
/persons/resource/persons204899

Jourdan,  Jacques-Henri
Group D. Dreyer, Max Planck Institute for Software Systems, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:1612.00277.pdf
(Preprint), 206KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Jourdan, J.-H. (2016). Sparsity Preserving Algorithms for Octagons. Retrieved from http://arxiv.org/abs/1612.00277.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-002D-21D6-C
Zusammenfassung
Known algorithms for manipulating octagons do not preserve their sparsity, leading typically to quadratic or cubic time and space complexities even if no relation among variables is known when they are all bounded. In this paper, we present new algorithms, which use and return octagons represented as weakly closed difference bound matrices, preserve the sparsity of their input and have better performance in the case their inputs are sparse. We prove that these algorithms are as precise as the known ones.