http://swrc.ontoware.org/ontology#TechnicalReport
Space Efficient and Output Sensitive Greedy Algorithms on Intervals
en
Department of Electrical and Electronic Engineering, Kobe University
Graduate School of Science and Engineering, Saitama University
Department of Computer Science, UBC
School of Information Science, JAIST
School of Information Science, JAIST
Graduate School of Science, Osaka Prefecture University
Department of Electrical Engineering and Computer Science, Iwate University
Toshiki Saitoh
Takashi Horiyama
David Kirkpatrick
Yota Otachi
Ryuhei Uehara
Yushi Uno
Katsuhisa Yamanaka
In this paper, we consider fundamental problems on the following machine model: An input is stored in read-only random-access memory, a limited random access workspace is available, and we report the output to a write-only media. We first propose efficient greedy algorithms using priority queues on the machine model as a general framework. Then, we apply the greedy algorithm to maximum independent set problem on intervals. Our algorithm runs in any workspace O(s) and it has the same time complexity of Snoeyink's algorithm which is the best known result if s = Ω(n).
In this paper, we consider fundamental problems on the following machine model: An input is stored in read-only random-access memory, a limited random access workspace is available, and we report the output to a write-only media. We first propose efficient greedy algorithms using priority queues on the machine model as a general framework. Then, we apply the greedy algorithm to maximum independent set problem on intervals. Our algorithm runs in any workspace O(s) and it has the same time complexity of Snoeyink's algorithm which is the best known result if s = Ω(n).
AN1009593X
研究報告アルゴリズム（AL）
2015-AL-154
4
1-7
2015-09-21
2188-8566