講演名 | 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 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 2014/7/2(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | 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) | 123 |
ページ範囲 | pp.- |
ページ数 | 4 |
発行日 |