Dominating Sets in Two-Directional Orthogonal Ray Graphs

	日本語 \| English

▶ 研究成果の引用やURL保存にあたっては、個々のアイテムのページ右上に表示されている「Permalink : http://hdl.handle.net/10258/xxxx」をお使いください。

室蘭工業大学の研究成果を検索・閲覧・ダウンロードできます


	トップ


	ランキング

インデックス

Permalink : http://hdl.handle.net/10258/00010202

File / Name	License
IEICETIS_98_8_1592_1595
IEICETIS_98_8_1592_1595 (102.33KB) [ 8 downloads ]

アイテムタイプ	学術雑誌論文 / Journal Article.
言語	英語
キーワード	Boolean-width, dominating set, dynamic programming, two-directional orthogonal ray graphs
著者	TAKAOKA Asahi TAYU Satoshi UENO Shuichi
著者（別表記）	髙岡旭田湯智上野修一
室蘭工業大学研究者データベースへのリンク	髙岡旭（TAKAOKA Asahi）
抄録	A 2-directional orthogonal ray graph is an intersection graph of rightward rays (half-lines) and downward rays in the plane. We show a dynamic programming algorithm that solves the weighted dominating set problem in O(n(3)) time for 2-directional orthogonal ray graphs, where n is the number of vertices of a graph.
雑誌名	IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
巻	E98D
号	8
ページ	1592 - 1595
発行年	2015
出版者	IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
出版者版へのリンク	10.1587/transinf.2015EDL8068
DOI	info:doi/10.1587/transinf.2015EDL8068
日本十進分類法	548
ISSN	1745-1361
権利	Copyright © 2015 IEICE
参考URL	IEICE Transactions Online TOP
著者版フラグ	publisher
フォーマット	application/pdf

-		本アーカイブに登録されているアイテムの著作権は、執筆者、出版社（学協会）などが有します。
-		本アーカイブに登録されているアイテムは、著作権法に規定されている私的使用や引用などの範囲内で利用してください。
-		著作権法に規定されている範囲を超える利用を行う場合には、著作権者の許諾を得てください。

室蘭工業大学附属図書館学術情報係
- 〒050-8585 北海道室蘭市水元町27-1
- TEL 0143-46-5191
- E-Mail gakujo@mmm.muroran-it.ac.jp

COUNTER