{"created":"2023-05-15T12:35:51.787445+00:00","id":4949,"links":{},"metadata":{"_buckets":{"deposit":"9bd73c1f-7562-417a-8a13-64114729f6cf"},"_deposit":{"created_by":91,"id":"4949","owners":[91],"pid":{"revision_id":0,"type":"depid","value":"4949"},"status":"published"},"_oai":{"id":"oai:nitech.repo.nii.ac.jp:00004949","sets":["31"]},"author_link":["8926","16289","15566","8926","16292"],"item_10001_biblio_info_28":{"attribute_name":"bibliographic_information","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2001-05-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"1255","bibliographicPageStart":"1244","bibliographicVolumeNumber":"E84-A","bibliographic_titles":[{"bibliographic_title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences","bibliographic_titleLang":"en"}]}]},"item_10001_description_36":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP  (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n) = O(t(n)ε) (ε < 1) using P(n) processors such that T(n)  P(n) = O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1  k  nε/2  (0  ε < 1) our algorithm runs in O((n log n)/p) time using p processors, where 1  p  n1-ε/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1  k  nε/2  (0  ε < 1), we propose an algorithm for computing the envelope layers of S  in O((n α(n) log3 n)/p) time using p  processors, where 1  p  n1-ε/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n  is ignored.","subitem_description_language":"en","subitem_description_type":"Other"}]},"item_10001_full_name_27":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"8926","nameIdentifierScheme":"WEKO"}],"names":[{"name":"和田, 幸一"}]}]},"item_10001_publisher_29":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers","subitem_publisher_language":"en"}]},"item_10001_source_id_30":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0916-8508","subitem_source_identifier_type":"ISSN"}]},"item_10001_source_id_32":{"attribute_name":"item_10001_source_id_32","attribute_value_mlt":[{"subitem_source_identifier":"AA10826239","subitem_source_identifier_type":"NCID"}]},"item_10001_version_type_33":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Castanho, Carla Denise","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"16289","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Chen, Wei","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"15566","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Wada, Koichi","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"8926","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Fujiwara, Akihiro","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"16292","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-01-25"}],"displaytype":"detail","filename":"E84-A_1244.pdf","filesize":[{"value":"677.5 kB"}],"format":"application/pdf","license_note":"Copyright (c) 2001 IEICE　http://search.ieice.org/index.html","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"本文_fulltext","url":"https://nitech.repo.nii.ac.jp/record/4949/files/E84-A_1244.pdf"},"version_id":"e3310c5e-5c88-4e97-8e3e-4bd04bfd0d56"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"item_resource_type","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Polynomially Fast Parallel Algorithms for Some P-Complete Problems","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Polynomially Fast Parallel Algorithms for Some P-Complete Problems","subitem_title_language":"en"}]},"item_type_id":"10001","owner":"91","path":["31"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2013-06-25"},"publish_date":"2013-06-25","publish_status":"0","recid":"4949","relation_version_is_last":true,"title":["Polynomially Fast Parallel Algorithms for Some P-Complete Problems"],"weko_creator_id":"91","weko_shared_id":-1},"updated":"2025-03-18T06:44:59.672309+00:00"}