文献

J-GLOBAL ID：201402235703372863   整理番号：14A0022712

2方向性直交レイグラフおよび関連グラフに関するノート

A Note on Two-Directional Orthogonal Ray Graphs and Related Graphs

著者 (3件)： TAKAOKA Asahi (Tokyo Inst. of Technol., Tokyo, JPN) ,  TAYU Satoshi (Tokyo Inst. of Technol., Tokyo, JPN) ,  UENO Shuichi (Tokyo Inst. of Technol., Tokyo, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 278(CAS2013 57-71)  ページ： 99-104  発行年： 2013年10月30日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 直交レイグラフは平面内の水平および垂直レイ(ハーフライン)の交差グラフである。もし各垂直レイが同じ方向であれば直交レイグラフは3方向性直交レイグラフである。もし各水平レイが同じ方向で各垂直レイも同じ方向であれば直交レイグラフは2方向性直交レイグラフである。筆者らはこれらのグラフの幾つかの構造的特性を導き,(重み付け)支配的集合の問題は2方向性直交レイグラフに対する多項式時間によって解けることを示した。また,誘導されたマッチング問題および強い辺彩色問題は3方向性直交レイグラフに対する多項式時間によって解けることを示した。更に,2方向性直交レイグラフの特殊な種類であるインターバル二分グラフに対する二次時間認識アルゴリズムを示した。(翻訳著者抄録)

シソーラス用語： *部分グラフ ,  *構造特性 ,  *計算理論 ,  時間 ,  マッチング ,  彩色問題
準シソーラス用語： グラフ彩色 ,  *二分グラフ ,  *多項式時間

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 2方向 ,  グラフ ,  ノート