WEKO3
インデックスリンク
アイテム
{"_buckets": {"deposit": "44d96bf1-9cd2-4d99-aa5f-c04626fe75a0"}, "_deposit": {"created_by": 3, "id": "9997", "owners": [3], "pid": {"revision_id": 0, "type": "depid", "value": "9997"}, "status": "published"}, "_oai": {"id": "oai:kanazawa-u.repo.nii.ac.jp:00009997", "sets": ["936"]}, "author_link": ["614"], "item_8_biblio_info_8": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2009-01-01", "bibliographicIssueDateType": "Issued"}, "bibliographicPageEnd": "2941", "bibliographicPageStart": "2938", "bibliographicVolumeNumber": "2009", "bibliographic_titles": [{"bibliographic_title": "Proceedings - IEEE International Symposium on Circuits and Systems"}]}]}, "item_8_description_21": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "We study the problem of embedding a guest graph into an optimally-sized grid with minimum edge-congestion. Based on a wellknown notion of graph separator, we prove that any guest graph can be embedded with a smaller edge-congestion as the guest graph has a smaller separator, and as the host grid has a higher dimension. Our results imply the following: An N-node planar graph with maximum node degree Δ can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ2 logN) if d = 2, O(Δ2 log logN) if d = 3, and O(Δ2) otherwise. An N-node graph with maximum node degree Δ and a treewidth O(1), such as a tree, an outerplanar graph, and a series-parallel graph, can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ) for d ≥ 2.", "subitem_description_type": "Abstract"}]}, "item_8_description_5": {"attribute_name": "提供者所属", "attribute_value_mlt": [{"subitem_description": "金沢大学理工研究域電子情報学系", "subitem_description_type": "Other"}]}, "item_8_publisher_17": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "IEEE = Institute of Electrical and Electronics Engineers"}]}, "item_8_version_type_25": {"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": "Matsubayashi, Akira"}], "nameIdentifiers": [{"nameIdentifier": "614", "nameIdentifierScheme": "WEKO"}, {"nameIdentifier": "10282378", "nameIdentifierScheme": "金沢大学研究者情報", "nameIdentifierURI": "http://ridb.kanazawa-u.ac.jp/public/detail.php?kaken=10282378"}, {"nameIdentifier": "10282378", "nameIdentifierScheme": "研究者番号", "nameIdentifierURI": "https://nrid.nii.ac.jp/nrid/1000010282378"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2017-10-03"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "TE-PR-MATSUBAYASHI-A-2938.pdf", "filesize": [{"value": "1.3 MB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 1300000.0, "url": {"label": "TE-PR-MATSUBAYASHI-A-2938.pdf", "url": "https://kanazawa-u.repo.nii.ac.jp/record/9997/files/TE-PR-MATSUBAYASHI-A-2938.pdf"}, "version_id": "3466daa2-80aa-401f-a888-da72b055fe30"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "conference paper", "resourceuri": "http://purl.org/coar/resource_type/c_5794"}]}, "item_title": "Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion"}]}, "item_type_id": "8", "owner": "3", "path": ["936"], "permalink_uri": "http://hdl.handle.net/2297/19124", "pubdate": {"attribute_name": "公開日", "attribute_value": "2017-10-03"}, "publish_date": "2017-10-03", "publish_status": "0", "recid": "9997", "relation": {}, "relation_version_is_last": true, "title": ["Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion"], "weko_shared_id": -1}
Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion
http://hdl.handle.net/2297/19124
http://hdl.handle.net/2297/1912443086d76-1b56-4176-ace0-e7717d6d01aa
名前 / ファイル | ライセンス | アクション |
---|---|---|
TE-PR-MATSUBAYASHI-A-2938.pdf (1.3 MB)
|
|
Item type | 会議発表論文 / Conference Paper(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2017-10-03 | |||||
タイトル | ||||||
タイトル | Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||
資源タイプ | conference paper | |||||
著者 |
Matsubayashi, Akira
× Matsubayashi, Akira |
|||||
提供者所属 | ||||||
内容記述タイプ | Other | |||||
内容記述 | 金沢大学理工研究域電子情報学系 | |||||
書誌情報 |
Proceedings - IEEE International Symposium on Circuits and Systems 巻 2009, p. 2938-2941, 発行日 2009-01-01 |
|||||
出版者 | ||||||
出版者 | IEEE = Institute of Electrical and Electronics Engineers | |||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | We study the problem of embedding a guest graph into an optimally-sized grid with minimum edge-congestion. Based on a wellknown notion of graph separator, we prove that any guest graph can be embedded with a smaller edge-congestion as the guest graph has a smaller separator, and as the host grid has a higher dimension. Our results imply the following: An N-node planar graph with maximum node degree Δ can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ2 logN) if d = 2, O(Δ2 log logN) if d = 3, and O(Δ2) otherwise. An N-node graph with maximum node degree Δ and a treewidth O(1), such as a tree, an outerplanar graph, and a series-parallel graph, can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ) for d ≥ 2. | |||||
著者版フラグ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 |