WEKO3
アイテム
Treewidth and related graph parameters
http://hdl.handle.net/10087/5142
http://hdl.handle.net/10087/5142acf3bf4a-006b-41a4-bfdd-6172516a6ead
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
Ph.D_E1-392.otachi.pdf (432.1 kB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2010-04-30 | |||||
| 著者 |
大舘, 陽太
× 大舘, 陽太 |
|||||
| タイトル | ||||||
| タイトル | Treewidth and related graph parameters | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| その他のタイトル | ||||||
| その他のタイトル | 木幅と関連グラフパラメータの研究 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Treewidth | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Spanning tree congestion | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | Security number of graphs | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 木幅 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | 全域本混雑度 | |||||
| キーワード | ||||||
| 主題Scheme | Other | |||||
| 主題 | グラフの安全数 | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_46ec | |||||
| 資源タイプ | thesis | |||||
| 著者(ヨミ) | ||||||
| 姓名 | オオタチ, ヨウタ | |||||
| 著者別名 | ||||||
| 姓名 | Otachi, Yota | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | For modeling some practical problems, graphs play very important roles.\nSince many modeled problems can be NP-hard in general, some restrictions\nfor inputs are required. Bounding a graph parameter of the inputs is one of\nthe successful approaches. We study this approach in this thesis. More precisely,\nwe study two graph parameters, spanning tree congestion and security\nnumber, that are related to treewidth.\nLet G be a connected graph and T be a spanning tree of G. For e ∈ E(T),\nthe congestion of e is the number of edges in G connecting two components\nof T − e. The edge congestion of G in T is the maximum congestion over all\nedges in T. The spanning tree congestion of G is the minimum congestion\nof G in its spanning trees. In this thesis, we show the spanning tree congestion\nfor the complete k-partite graphs, the two-dimensional tori, and the twodimensional\nHamming graphs. We also address lower bounds of spanning\ntree congestion for the multi-dimensional hypercubes, the multi-dimensional\ngrids, and the multi-dimensional Hamming graphs.\nThe security number of a graph is the cardinality of a smallest vertex subset\nof the graph such that any “attack” on the subset is “defendable.” In this thesis,\nwe determine the security number of two-dimensional cylinders and tori.\nThis result settles a conjecture of Brigham, Dutton and Hedetniemi [Discrete\nAppl. Math. 155 (2007) 1708–1714]. We also show that every outerplanar\ngraph has security number at most three. Additionally, we present lower and\nupper bounds for some classes of graphs. | |||||
| 内容記述 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 学位記番号：工博甲392 | |||||
| 書誌情報 | p. viii, 60p., 発行日 2010-03 | |||||
| フォーマット | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | application/pdf | |||||
| 著者版フラグ | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
| 出版者 | ||||||
| 出版者 | 群馬大学工学研究科 | |||||
| 資源タイプ | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | Thesis or Dissertation | |||||
| 学位名 | ||||||
| 学位名 | 博士（工学） | |||||
| 学位授与機関 | ||||||
| 学位授与機関名 | 群馬大学 | |||||
| 学位授与年月日 | ||||||
| 学位授与年月日 | 2010-03-24 | |||||
| 学位授与番号 | ||||||
| 学位授与番号 | 12301甲第392号 | |||||
| 更新日 | ||||||
| 値 | 2019-12-04 | |||||
