ログイン
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究者名(五十音順)
  2. 髙岡 旭(TAKAOKA Asahi)
  1. 学術雑誌論文

Dominating Sets and Induced Matchings in Orthogonal Ray Graphs

http://hdl.handle.net/10258/00010204
http://hdl.handle.net/10258/00010204
29d2f7e7-8fac-4b2d-84b3-0d29127a99c3
名前 / ファイル ライセンス アクション
IEICETIS_97_12_3101_3109.pdf IEICETIS_97_12_3101_3109 (347.8 kB)
Item type 学術雑誌論文 / Journal Article.(1)
公開日 2020-06-25
書誌情報 en : IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS

巻 E97D, 号 12, p. 3101-3109, 発行日 2014
タイトル
タイトル Dominating Sets and Induced Matchings in Orthogonal Ray Graphs
言語 en
言語
言語 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
著者 髙岡, 旭

× 髙岡, 旭

ja 髙岡, 旭

en TAKAOKA, Asahi

ja-Kana タカオカ, アサヒ


Search repository
田湯, 智

× 田湯, 智

en TAYU, Satoshi

ja 田湯, 智

ja-Kana タユ, サトシ


Search repository
上野, 修一

× 上野, 修一

en UENO, Shuichi

ja 上野, 修一

ja-Kana ウエノ, シュウイチ


Search repository
室蘭工業大学研究者データベースへのリンク
表示名 髙岡 旭(TAKAOKA Asahi)
URL 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
出版者
出版者 IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
言語 en
出版者版へのリンク
表示名 10.1587/transinf.2014EDP7184
URL 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
戻る
0
views
See details
Views

Versions

Ver.1 2023-06-19 11:08:55.774168
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR 2.0
  • OAI-PMH JPCOAR 1.0
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3