講演抄録/キーワード |
講演名 |
2012-10-31 14:40
On 1 + $\epsilon$ strip graphs Takashi Hayashi(Gunma Univ.)・○Hidehiro Shinohara(Tohoku Univ.)・Koichi Yamazaki(Gunma Univ.) COMP2012-39 |
抄録 |
(和) |
単位円グラフ$G$が$\varepsilon$-strip グラフとは,
すべての単位円の中心点が幅$\varepsilon$の帯に収まるような表現を
$G$が持つ時を言う.
本稿ではグラフクラス$\bigcap_{\varepsilon > 0} L(\varepsilon)$に関する
基本的な結果について述べる,
ここで$L(\varepsilon)$は$\varepsilon$-strip グラフの集合を意味する. |
(英) |
A unit disk graph $G$ is called an $\varepsilon$-strip graph,
if all center points of the disks lie
in a parallel strip of width $\varepsilon$.
We discuss some fundamental results on the graph class
$\bigcap_{\varepsilon > 0} L(\varepsilon)$, where
$L(\varepsilon)$ denotes the $\varepsilon$-strip graphs. |
キーワード |
(和) |
strip グラフ / 単位円グラフ / 禁止誘導部分グラフ / / / / / |
(英) |
strip graph / unit disk graph / forbidden induced subgraph / / / / / |
文献情報 |
信学技報, vol. 112, no. 272, COMP2012-39, pp. 33-36, 2012年10月. |
資料番号 |
COMP2012-39 |
発行日 |
2012-10-24 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-39 |