{"created":"2021-03-01T06:05:34.658526+00:00","id":1894,"links":{},"metadata":{"_buckets":{"deposit":"a960be92-95f3-4b0d-b932-80401f12aee2"},"_deposit":{"id":"1894","owners":[],"pid":{"revision_id":0,"type":"depid","value":"1894"},"status":"published"},"_oai":{"id":"oai:niigata-u.repo.nii.ac.jp:00001894","sets":["423:424:425","453:454"]},"item_5_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2000-06","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"6","bibliographicPageEnd":"1227","bibliographicPageStart":"1222","bibliographicVolumeNumber":"E83-A","bibliographic_titles":[{"bibliographic_title":"IEICE transactions on fundamentals of electronics, communications and computer sciences"},{"bibliographic_title":"IEICE transactions on fundamentals of electronics, communications and computer sciences","bibliographic_titleLang":"en"}]}]},"item_5_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"In a multihop network, radio packets are often relayed through inter-mediate stations (repeaters) in order to transfer a radio packet from a source to its destination. We consider a scheduling problem in a multihop network using a graphtheoretical model. Let D=(V,A) be the digraph with a vertex set V and an arc set A. Let f be a labeling of positive integers on the arcs of A. The value of f(u,v) means a frequency band assigned on the link from u to v. We call f antitransitive if f(u,v) ≠ f(v,w) for any adjacent arcs (u,v) and (v,w) of D. The minimum antitransitive-labeling problem is the problem of finding a minimum antitransitive-labeling such that the number of integers assigned in an antitransitive labeling is minimum. In this paper, we prove that this problem is NP-hard, and we propose a simple distributed approximation algorithm for it.","subitem_description_type":"Abstract"}]},"item_5_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"6113","nameIdentifierScheme":"WEKO"}],"names":[{"name":"仙石, 正和"}]},{"nameIdentifiers":[{"nameIdentifier":"5597","nameIdentifierScheme":"WEKO"}],"names":[{"name":"中野, 敬介"}]}]},"item_5_publisher_7":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"The Institute of Electronics, Information and Communication Engineers"}]},"item_5_relation_31":{"attribute_name":"異版である","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"http://www.ieice.org/jpn/trans_online/","subitem_relation_type_select":"URI"}}]},"item_5_rights_15":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"copyright©2000 IEICE"}]},"item_5_select_19":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_5_source_id_11":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA10826239","subitem_source_identifier_type":"NCID"}]},"item_5_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"09168508","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Watanabe, Kaoru"}],"nameIdentifiers":[{"nameIdentifier":"6108","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Sengoku, Masakazu"}],"nameIdentifiers":[{"nameIdentifier":"6109","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Tamura, Hiroshi"}],"nameIdentifiers":[{"nameIdentifier":"6110","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Nakano, Keisuke"}],"nameIdentifiers":[{"nameIdentifier":"5597","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Shinoda, Shoji"}],"nameIdentifiers":[{"nameIdentifier":"5445","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-07-29"}],"displaytype":"detail","filename":"e83-a_6_1222.pdf","filesize":[{"value":"606.3 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"e83-a_6_1222.pdf","url":"https://niigata-u.repo.nii.ac.jp/record/1894/files/e83-a_6_1222.pdf"},"version_id":"01449ea6-4c7f-4ac4-af04-1471074bbef6"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"multihop network","subitem_subject_scheme":"Other"},{"subitem_subject":"mobile communication","subitem_subject_scheme":"Other"},{"subitem_subject":"graph theory","subitem_subject_scheme":"Other"},{"subitem_subject":"NP-complete problem","subitem_subject_scheme":"Other"},{"subitem_subject":"cut covering","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"A Scheduling Problem in Multihop Networks","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"A Scheduling Problem in Multihop Networks"},{"subitem_title":"A Scheduling Problem in Multihop Networks","subitem_title_language":"en"}]},"item_type_id":"5","owner":"1","path":["454","425"],"pubdate":{"attribute_name":"公開日","attribute_value":"2008-07-31"},"publish_date":"2008-07-31","publish_status":"0","recid":"1894","relation_version_is_last":true,"title":["A Scheduling Problem in Multihop Networks"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2022-12-15T03:34:42.893479+00:00"}