16 citations · 57 across the 26 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.CC2015
The Shortest Path Problem with Edge Information Reuse is NP-Complete
Jesper Larsson Träff
We show that the following variation of the single-source shortest path problem is NP-complete. Let a weighted, directed, acyclic graph with source and sink vertices $s…
cs.DS2015★ 1 cited
Polynomial-time Construction of Optimal Tree-structured Communication Data Layout Descriptions
Robert Ganian, Martin Kalany, Stefan Szeider +1
We show that the problem of constructing tree-structured descriptions of data layouts that are optimal with respect to space or other criteria from given sequences of displacements…
cs.DS2015
The Lock-free -LSM Relaxed Priority Queue
Martin Wimmer, Jakob Gruber, Jesper Larsson Träff +1
Priority queues are data structures which store keys in an ordered fashion to allow efficient access to the minimal (maximal) key. Priority queues are essential for many applicatio…