WEKO3
アイテム
{"_buckets": {"deposit": "7d9de6d6-7c12-49d8-9062-d243e2907fe9"}, "_deposit": {"created_by": 18, "id": "10263", "owners": [18], "pid": {"revision_id": 0, "type": "depid", "value": "10263"}, "status": "published"}, "_oai": {"id": "oai:muroran-it.repo.nii.ac.jp:00010263", "sets": ["46", "489"]}, "author_link": ["57709", "57701", "59462"], "item_79_biblio_info_10": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2014", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "12", "bibliographicPageEnd": "3109", "bibliographicPageStart": "3101", "bibliographicVolumeNumber": "E97D", "bibliographic_titles": [{"bibliographic_title": "IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS", "bibliographic_titleLang": "en"}]}]}, "item_79_description_23": {"attribute_name": "フォーマット", "attribute_value_mlt": [{"subitem_description": "application/pdf", "subitem_description_type": "Other"}]}, "item_79_description_7": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "An orthogonal ray graph is an intersection graph of horizontal and vertical rays (closed half-lines) in the plane. Such a graph is 3-directional if every vertical ray has the same direction, and 2-directional if every vertical ray has the same direction and every horizontal ray has the same direction. We derive some structural properties of orthogonal ray graphs, and based on these properties, we introduce polynomial-time algorithms that solve the dominating set problem, the induced matching problem, and the strong edge coloring problem for these graphs. We show that for 2-directional orthogonal ray graphs, the dominating set problem can be solved in O(n(2) log(5) n) time, the weighted dominating set problem can be solved in O(n(4) log n) time, and the number of dominating sets of a fixed size can be computed in O(n(6) log n) time, where n is the number of vertices in the graph. We also show that for 2-directional orthogonal ray graphs, the weighted induced matching problem and the strong edge coloring problem can be solved in O(n(2) + m log n) time, where m is the number of edges in the graph. Moreover, we show that for 3-directional orthogonal ray graphs, the induced matching problem can be solved in O(m(2)) time, the weighted induced matching problem can be solved in O(m(4)) time, and the strong edge coloring problem can be solved in O(m(3)) time. We finally show that the weighted induced matching problem can be solved in O(m(6)) time for orthogonal ray graphs.", "subitem_description_language": "en", "subitem_description_type": "Abstract"}]}, "item_79_link_17": {"attribute_name": "出版者版へのリンク", "attribute_value_mlt": [{"subitem_link_text": "10.1587/transinf.2014EDP7184", "subitem_link_url": "https://doi.org/10.1587/transinf.2014EDP7184"}]}, "item_79_link_5": {"attribute_name": "室蘭工業大学研究者データベースへのリンク", "attribute_value_mlt": [{"subitem_link_text": "髙岡 旭(TAKAOKA Asahi)", "subitem_link_url": "http://rdsoran.muroran-it.ac.jp/html/200000242_ja.html"}]}, "item_79_publisher_11": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG", "subitem_publisher_language": "en"}]}, "item_79_relation_18": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type": "isIdenticalTo", "subitem_relation_type_id": {"subitem_relation_type_id_text": "10.1587/transinf.2014EDP7184", "subitem_relation_type_select": "DOI"}}]}, "item_79_relation_20": {"attribute_name": "参考URL", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_language": "en", "subitem_relation_name_text": "IEICE Transactions Online TOP"}], "subitem_relation_type_id": {"subitem_relation_type_id_text": "https://search.ieice.org/index.html", "subitem_relation_type_select": "URI"}}]}, "item_79_rights_19": {"attribute_name": "権利", "attribute_value_mlt": [{"subitem_rights": "Copyright © 2014 IEICE", "subitem_rights_language": "en"}]}, "item_79_source_id_12": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "1745-1361", "subitem_source_identifier_type": "EISSN"}]}, "item_79_subject_9": {"attribute_name": "日本十進分類法", "attribute_value_mlt": [{"subitem_subject": "548", "subitem_subject_scheme": "NDC"}]}, "item_79_text_4": {"attribute_name": "著者ID(非表示)", "attribute_value_mlt": [{"subitem_text_value": "20999401"}]}, "item_79_version_type_21": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_version_resource": "http://purl.org/coar/version/c_970fb48d4fbd8a85", "subitem_version_type": "VoR"}]}, "item_access_right": {"attribute_name": "アクセス権", "attribute_value_mlt": [{"subitem_access_right": "open access", "subitem_access_right_uri": "http://purl.org/coar/access_right/c_abf2"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorAffiliations": [{"affiliationNameIdentifiers": [{"affiliationNameIdentifier": "10103", "affiliationNameIdentifierScheme": "kakenhi"}], "affiliationNames": [{"affiliationName": "室蘭工業大学", "affiliationNameLang": "ja"}, {"affiliationName": "Muroran Institute of Technology", "affiliationNameLang": "en"}]}], "creatorNames": [{"creatorName": "髙岡, 旭", "creatorNameLang": "ja"}, {"creatorName": "TAKAOKA, Asahi", "creatorNameLang": "en"}, {"creatorName": "タカオカ, アサヒ", "creatorNameLang": "ja-Kana"}], "familyNames": [{"familyName": "髙岡", "familyNameLang": "ja"}, {"familyName": "TAKAOKA", "familyNameLang": "en"}, {"familyName": "タカオカ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "旭", "givenNameLang": "ja"}, {"givenName": "Asahi", "givenNameLang": "en"}, {"givenName": "アサヒ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "59462", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "1000060783587", "nameIdentifierScheme": "NRID", "nameIdentifierURI": "https://nrid.nii.ac.jp/ja/nrid/1000060783587"}]}, {"creatorAffiliations": [{"affiliationNameIdentifiers": [], "affiliationNames": [{"affiliationName": "", "affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "TAYU, Satoshi", "creatorNameLang": "en"}, {"creatorName": "田湯, 智", "creatorNameLang": "ja"}, {"creatorName": "タユ, サトシ", "creatorNameLang": "ja-Kana"}], "familyNames": [{"familyName": "TAYU", "familyNameLang": "en"}, {"familyName": "田湯", "familyNameLang": "ja"}, {"familyName": "タユ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Satoshi", "givenNameLang": "en"}, {"givenName": "智", "givenNameLang": "ja"}, {"givenName": "サトシ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "57701", "nameIdentifierScheme": "WEKO"}]}, {"creatorAffiliations": [{"affiliationNameIdentifiers": [], "affiliationNames": [{"affiliationName": "", "affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "UENO, Shuichi", "creatorNameLang": "en"}, {"creatorName": "上野, 修一", "creatorNameLang": "ja"}, {"creatorName": "ウエノ, シュウイチ", "creatorNameLang": "ja-Kana"}], "familyNames": [{"familyName": "UENO", "familyNameLang": "en"}, {"familyName": "上野", "familyNameLang": "ja"}, {"familyName": "ウエノ", "familyNameLang": "ja-Kana"}], "givenNames": [{"givenName": "Shuichi", "givenNameLang": "en"}, {"givenName": "修一", "givenNameLang": "ja"}, {"givenName": "シュウイチ", "givenNameLang": "ja-Kana"}], "nameIdentifiers": [{"nameIdentifier": "57709", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2020-06-25"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "IEICETIS_97_12_3101_3109.pdf", "filesize": [{"value": "347.8 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_note", "mimetype": "application/pdf", "size": 347800.0, "url": {"label": "IEICETIS_97_12_3101_3109", "objectType": "fulltext", "url": "https://muroran-it.repo.nii.ac.jp/record/10263/files/IEICETIS_97_12_3101_3109.pdf"}, "version_id": "9d99742e-d261-4b15-a508-0f8a3213088b"}]}, "item_keyword": {"attribute_name": "キーワード", "attribute_value_mlt": [{"subitem_subject": "boolean-width", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "dominating set", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "induced matching", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "orthogonal ray graphs", "subitem_subject_language": "en", "subitem_subject_scheme": "Other"}, {"subitem_subject": "strong edge coloring", "subitem_subject_language": "en", "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": "Dominating Sets and Induced Matchings in Orthogonal Ray Graphs", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Dominating Sets and Induced Matchings in Orthogonal Ray Graphs", "subitem_title_language": "en"}]}, "item_type_id": "79", "owner": "18", "path": ["46", "489"], "permalink_uri": "http://hdl.handle.net/10258/00010204", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2020-06-25"}, "publish_date": "2020-06-25", "publish_status": "0", "recid": "10263", "relation": {}, "relation_version_is_last": true, "title": ["Dominating Sets and Induced Matchings in Orthogonal Ray Graphs"], "weko_shared_id": -1}
Dominating Sets and Induced Matchings in Orthogonal Ray Graphs
http://hdl.handle.net/10258/00010204
http://hdl.handle.net/10258/0001020429d2f7e7-8fac-4b2d-84b3-0d29127a99c3
名前 / ファイル | ライセンス | アクション |
---|---|---|
IEICETIS_97_12_3101_3109 (347.8 kB)
|
|
Item type | 学術雑誌論文 / Journal Article.(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2020-06-25 | |||||||||||
タイトル | ||||||||||||
言語 | en | |||||||||||
タイトル | Dominating Sets and Induced Matchings in Orthogonal Ray Graphs | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
キーワード | ||||||||||||
言語 | en | |||||||||||
主題Scheme | Other | |||||||||||
主題 | boolean-width | |||||||||||
キーワード | ||||||||||||
言語 | en | |||||||||||
主題Scheme | Other | |||||||||||
主題 | dominating set | |||||||||||
キーワード | ||||||||||||
言語 | en | |||||||||||
主題Scheme | Other | |||||||||||
主題 | induced matching | |||||||||||
キーワード | ||||||||||||
言語 | en | |||||||||||
主題Scheme | Other | |||||||||||
主題 | orthogonal ray graphs | |||||||||||
キーワード | ||||||||||||
言語 | en | |||||||||||
主題Scheme | Other | |||||||||||
主題 | strong edge coloring | |||||||||||
資源タイプ | ||||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
資源タイプ | journal article | |||||||||||
アクセス権 | ||||||||||||
アクセス権 | open access | |||||||||||
アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||
著者 |
髙岡, 旭
× 髙岡, 旭
WEKO
59462
× 田湯, 智× 上野, 修一 |
|||||||||||
室蘭工業大学研究者データベースへのリンク | ||||||||||||
髙岡 旭(TAKAOKA Asahi) | ||||||||||||
http://rdsoran.muroran-it.ac.jp/html/200000242_ja.html | ||||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | An orthogonal ray graph is an intersection graph of horizontal and vertical rays (closed half-lines) in the plane. Such a graph is 3-directional if every vertical ray has the same direction, and 2-directional if every vertical ray has the same direction and every horizontal ray has the same direction. We derive some structural properties of orthogonal ray graphs, and based on these properties, we introduce polynomial-time algorithms that solve the dominating set problem, the induced matching problem, and the strong edge coloring problem for these graphs. We show that for 2-directional orthogonal ray graphs, the dominating set problem can be solved in O(n(2) log(5) n) time, the weighted dominating set problem can be solved in O(n(4) log n) time, and the number of dominating sets of a fixed size can be computed in O(n(6) log n) time, where n is the number of vertices in the graph. We also show that for 2-directional orthogonal ray graphs, the weighted induced matching problem and the strong edge coloring problem can be solved in O(n(2) + m log n) time, where m is the number of edges in the graph. Moreover, we show that for 3-directional orthogonal ray graphs, the induced matching problem can be solved in O(m(2)) time, the weighted induced matching problem can be solved in O(m(4)) time, and the strong edge coloring problem can be solved in O(m(3)) time. We finally show that the weighted induced matching problem can be solved in O(m(6)) time for orthogonal ray graphs. | |||||||||||
言語 | en | |||||||||||
書誌情報 |
en : IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 巻 E97D, 号 12, p. 3101-3109, 発行日 2014 |
|||||||||||
出版者 | ||||||||||||
言語 | en | |||||||||||
出版者 | IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG | |||||||||||
出版者版へのリンク | ||||||||||||
10.1587/transinf.2014EDP7184 | ||||||||||||
https://doi.org/10.1587/transinf.2014EDP7184 | ||||||||||||
DOI | ||||||||||||
関連タイプ | isIdenticalTo | |||||||||||
識別子タイプ | DOI | |||||||||||
関連識別子 | 10.1587/transinf.2014EDP7184 | |||||||||||
日本十進分類法 | ||||||||||||
主題Scheme | NDC | |||||||||||
主題 | 548 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | EISSN | |||||||||||
収録物識別子 | 1745-1361 | |||||||||||
権利 | ||||||||||||
言語 | en | |||||||||||
権利情報 | Copyright © 2014 IEICE | |||||||||||
参考URL | ||||||||||||
識別子タイプ | URI | |||||||||||
関連識別子 | https://search.ieice.org/index.html | |||||||||||
言語 | en | |||||||||||
関連名称 | IEICE Transactions Online TOP | |||||||||||
著者版フラグ | ||||||||||||
出版タイプ | VoR | |||||||||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||
フォーマット | ||||||||||||
内容記述タイプ | Other | |||||||||||
内容記述 | application/pdf |