2024-02-27T09:30:23Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001451132023-04-27T10:00:04Z01164:02592:07834:08333
Space Efficient and Output Sensitive Greedy Algorithms on IntervalsSpace Efficient and Output Sensitive Greedy Algorithms on Intervalsenghttp://id.nii.ac.jp/1001/00145080/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=145113&item_no=1&attribute_id=1&file_no=1Copyright (c) 2015 by the Information Processing Society of JapanDepartment of Electrical and Electronic Engineering, Kobe UniversityGraduate School of Science and Engineering, Saitama UniversityDepartment of Computer Science, UBCSchool of Information Science, JAISTSchool of Information Science, JAISTGraduate School of Science, Osaka Prefecture UniversityDepartment of Electrical Engineering and Computer Science, Iwate UniversityToshiki, SaitohTakashi, HoriyamaDavid, KirkpatrickYota, OtachiRyuhei, UeharaYushi, UnoKatsuhisa, YamanakaIn 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-1544172015-09-212188-85662015-09-11