| 講演名 | 2014-07-09 Weighted Dominating Sets and Induced Matchings in Orthogonal Ray Graphs , |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | An orthogonal ray graph is an intersection graph of horizontal rays (closed half-lines) and vertical rays in the plane. A 2-directional orthogonal ray graph is an intersection graph of rightward rays and downward rays. We recently showed in [12] that the weighted dominating set problem can be solved in O(n^4 log n) time for vertex-weighted 2-directional orthogonal ray graphs by using a new parameter, boolean-width of graphs, where n is the number of vertices in a graph. We improve the result by showing an O(n^3)-time algorithm to solve the problem based on a direct dynamic programming approach. We also show that the weighted induced matching problem can be solved in O(m^6) time for edge-weighted orthogonal ray graphs, where m is the number of edges in a graph. |
| キーワード(和) | |
| キーワード(英) | Boolean-width / Dominating set / Dynamic programming / Induced matching / Orthogonal ray graphs |
| 資料番号 | CAS2014-10,VLD2014-19,SIP2014-31,MSS2014-10,SIS2014-10 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SIP |
|---|---|
| 開催期間 | 2014/7/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Signal Processing (SIP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Weighted Dominating Sets and Induced Matchings in Orthogonal Ray Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / Boolean-width |
| 第 1 著者 氏名（和/英） | / Asahi TAKAOKA |
| 第 1 著者 所属（和/英） | Department of Communications and Computer Engineering, Tokyo Institute of Technology |
| 発表年月日 | 2014-07-09 |
| 資料番号 | CAS2014-10,VLD2014-19,SIP2014-31,MSS2014-10,SIS2014-10 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 124 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |