{"created":"2025-01-18T23:44:55.674212+00:00","updated":"2025-01-21T12:20:36.042354+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00098738","sets":["1164:2592:7425:7467"]},"path":["7467"],"owner":"11","recid":"98738","title":["Toward Constant Time Enumeration"],"pubdate":{"attribute_name":"公開日","attribute_value":"2014-02-24"},"_buckets":{"deposit":"d578eaa4-549b-419d-a9e0-cb0fe8d9a4fb"},"_deposit":{"id":"98738","pid":{"type":"depid","value":"98738","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"Toward Constant Time Enumeration","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Toward Constant Time Enumeration"},{"subitem_title":"Toward Constant Time Enumeration","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2014-02-24","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"National Institute of Informatics"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"National Institute of Informatics","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/98738/files/IPSJ-AL14147017.pdf"},"date":[{"dateType":"Available","dateValue":"2016-02-24"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL14147017.pdf","filesize":[{"value":"677.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"d9243b49-9256-45d8-8ee2-3cf86c4e7607","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2014 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takeaki, Uno"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takeaki, Uno","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"In this paper, we propose a new amortized analysis for enumeration algorithms. We amortize the computation time of an iteration by charging to all its descendant iterations. We clarify sufficient conditions such that if an enumeration algorithm satisfies the condition, the amortized analysis works. By the amortization, we show that many elimination orderings, matchings in a graph, connected vertex induced subgraphs in a graph, and spanning trees can be enumerated in O(1) time for each solution with simple algorithms and proofs.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"In this paper, we propose a new amortized analysis for enumeration algorithms. We amortize the computation time of an iteration by charging to all its descendant iterations. We clarify sufficient conditions such that if an enumeration algorithm satisfies the condition, the amortized analysis works. By the amortization, we show that many elimination orderings, matchings in a graph, connected vertex induced subgraphs in a graph, and spanning trees can be enumerated in O(1) time for each solution with simple algorithms and proofs.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2014-02-24","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"17","bibliographicVolumeNumber":"2014-AL-147"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"id":98738,"links":{}}