Studies on multigraph connectivity augmentation problems 多重グラフにおける連結度増大問題に関する研究
この論文にアクセスする
この論文をさがす
著者
書誌事項
- タイトル
-
Studies on multigraph connectivity augmentation problems
- タイトル別名
-
多重グラフにおける連結度増大問題に関する研究
- 著者名
-
石井, 利昌
- 著者別名
-
イシイ, トシマサ
- 学位授与大学
-
京都大学
- 取得学位
-
博士 (情報学)
- 学位授与番号
-
甲第8483号
- 学位授与年月日
-
2000-03-23
注記・抄録
博士論文
目次
- 論文目録 / (0001.jp2)
- Contents / p5 (0008.jp2)
- 1 Introduction / p1 (0010.jp2)
- 1.1 Introduction / p1 (0010.jp2)
- 1.2 Basic definitions / p3 (0011.jp2)
- 1.3 Historical background / p5 (0012.jp2)
- 1.4 Structure of this thesis / p11 (0015.jp2)
- 2 Preliminaries / p13 (0016.jp2)
- 2.1 Definitions / p13 (0016.jp2)
- 2.2 Properties of k-Vertex-Connected Multigraphs / p14 (0017.jp2)
- 2.3 Edge-Splitting / p19 (0019.jp2)
- 2.4 Edge-Shifting / p25 (0022.jp2)
- 2.5 Lower Bounds on the Optimum Value of EVAP / p27 (0023.jp2)
- 3 Augmenting an Arbitrary Multigraph to an rλ-Edge-Connected and Biconnected Multigraph / p31 (0025.jp2)
- 3.1 Introduction / p31 (0025.jp2)
- 3.2 Lower bounds / p31 (0025.jp2)
- 3.3 Algorithm for EVAP(rλ,2) / p33 (0026.jp2)
- 3.4 Justification of Step I / p36 (0028.jp2)
- 3.5 Justification of Step II / p40 (0030.jp2)
- 3.6 Justification of Step III / p41 (0030.jp2)
- 3.7 Justification of Step IV / p43 (0031.jp2)
- 3.8 Case of EVAP(ℓ,2) / p46 (0033.jp2)
- 3.9 Preserving simplicity / p48 (0034.jp2)
- 3.10 Conclusion / p52 (0036.jp2)
- 4 Augmenting a Biconnected Multigraph to an ℓ-Edge-Connected and Triconnected Multigraph / p53 (0036.jp2)
- 4.1 Introduction / p53 (0036.jp2)
- 4.2 Lower bounds / p53 (0036.jp2)
- 4.3 Algorithm for EVAP(ℓ,3)in a Biconnected Multigraph / p55 (0037.jp2)
- 4.4 Justification of Step I / p62 (0041.jp2)
- 4.5 Justification of Step II / p70 (0045.jp2)
- 4.6 Justification of Step III / p70 (0045.jp2)
- 4.7 Justification of Step IV / p79 (0049.jp2)
- 4.8 Justification of Step V / p86 (0053.jp2)
- 4.9 Conclusion / p94 (0057.jp2)
- 5 Augmenting an Arbitrary Multigraph to an ℓ-Edge-Connected and Triconnected Multigraph / p95 (0057.jp2)
- 5.1 Introduction / p95 (0057.jp2)
- 5.2 Lower bounds / p97 (0058.jp2)
- 5.3 Algorithm for EVAP(ℓ,3) / p97 (0058.jp2)
- 5.4 Justification of Step I / p103 (0061.jp2)
- 5.5 Justification of Step II / p108 (0064.jp2)
- 5.6 Justification of Step III / p111 (0065.jp2)
- 5.7 Justification of Step IV / p113 (0066.jp2)
- 5.8 Conclusion / p114 (0067.jp2)
- 6 Augmenting a (k-ℓ)-Vertex-Connected Multigraph to an ℓ-Edge-Connected and k-Vertex-Connected Multigraph / p115 (0067.jp2)
- 6.1 Introduction / p115 (0067.jp2)
- 6.2 Lower bounds / p115 (0067.jp2)
- 6.3 Algorithm for EVAP(ℓ,k) / p117 (0068.jp2)
- 6.4 Justification of Step I / p120 (0070.jp2)
- 6.5 Justification of Step II / p121 (0070.jp2)
- 6.6 Complexity of Step III / p126 (0073.jp2)
- 6.7 Conclusion / p126 (0073.jp2)
- 7 Conclusion / p127 (0073.jp2)
