お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2008-03-10 15:55
外平面グラフに対するsecurity number
小澤恭平大舘陽太山崎浩一群馬大COMP2007-64
抄録 (和) $G=(V,E)$をグラフとし,$S = \{s_1,s_2,\ldots,s_k\}$を$V$の部分集合とする.
$S$上の\textbf{攻撃}とは,
$1 \le i \le k$に対して$A_i \subseteq N[s_i] - S$であるような,
互いに素な$k$個の集合$\mathscr{A} = \{A_1,A_2,\ldots,A_k\}$であり,
$S$上の\textbf{防御}とは,
$1 \le i \le k$に対して$D_i \subseteq N[s_i] \cap S$であるような,
互いに素な$k$個の集合$\mathscr{D} = \{D_1,D_2,\ldots,D_k\}$である.
ここで,$v$の閉近傍を$N[v]$とかく.
このとき,攻撃$\mathscr{A}$が\textbf{防御可能}とは,
ある防御$\mathscr{D}$が存在し,
$1 \le i \le k$に対して,$|D_i| \ge |A_i|$を満たすことをいう.
そして,$S$が\textbf{セキュア}とは,
$S$上の全ての攻撃が防御可能であることをいう.
$G$の\textbf{セキュリティ数}とは,$G$の最小なセキュア集合の大きさである.
本論文では,任意の外平面グラフに対して,そのセキュリティ数が高々3であることを示す. 
(英) Let $G=(V,E)$ be a graph and $S = \{s_1,s_2,\ldots,s_k\}$ be a subset
of $V$.
An \textit{attack} on $S$ is any $k$ mutually disjoint sets
$\mathscr{A} = \{A_1,A_2,\ldots,A_k\}$ such that
$A_i \subseteq N[s_i] - S$ for $1 \le i \le k$, and
a \textit{defense} of $S$ is any $k$ mutually disjoint sets
$\mathscr{D} = \{D_1,D_2,\ldots,D_k\}$ such that
$D_i \subseteq N[s_i] \cap S$ for $1 \le i \le k$,
where $N[v]$ denotes the closed neighborhood of $v$.
Then attack $\mathscr{A}$ is said to be \textit{defendable}
if there exists a defense $\mathscr{D}$ such that $|D_i| \ge |A_i|$
for $1 \le i \le k$, and
$S$ is \textit{secure} if every attack on $S$ is defendable.
The \textit{security number} of $G$ is the cardinality of
a smallest secure set of $G$.
In this paper, we show that any outerplanar graph has security number
at most 3.
キーワード (和) 外平面グラフ / セキュリティ数 / / / / / /  
(英) Outerplanar graph / Security number / / / / / /  
文献情報 信学技報, vol. 107, no. 537, COMP2007-64, pp. 63-65, 2008年3月.
資料番号 COMP2007-64 
発行日 2008-03-03 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2007-64

研究会情報
研究会 COMP  
開催期間 2008-03-10 - 2008-03-10 
開催地(和) 日本アイ・ビー・エム(株)大和事業所 
開催地(英)  
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2008-03-COMP 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) 外平面グラフに対するsecurity number 
サブタイトル(和)  
タイトル(英) Security number for outerplanar graphs 
サブタイトル(英)  
キーワード(1)(和/英) 外平面グラフ / Outerplanar graph  
キーワード(2)(和/英) セキュリティ数 / Security number  
キーワード(3)(和/英) /  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 小澤 恭平 / Kyohei Kozawa / コザワ キョウヘイ
第1著者 所属(和/英) 群馬大学 (略称: 群馬大)
Gunma University (略称: Gunma Univ.)
第2著者 氏名(和/英/ヨミ) 大舘 陽太 / Yota Otachi / オオタチ ヨウタ
第2著者 所属(和/英) 群馬大学 (略称: 群馬大)
Gunma University (略称: Gunma Univ.)
第3著者 氏名(和/英/ヨミ) 山崎 浩一 / Koichi Yamazaki / ヤマザキ コウイチ
第3著者 所属(和/英) 群馬大学 (略称: 群馬大)
Gunma University (略称: Gunma Univ.)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2008-03-10 15:55:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2007-64 
巻番号(vol) IEICE-107 
号番号(no) no.537 
ページ範囲 pp.63-65 
ページ数 IEICE-3 
発行日 IEICE-COMP-2008-03-03 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会