Studies on multigraph connectivity augmentation problems 多重グラフにおける連結度増大問題に関する研究

この論文をさがす

著者

    • 石井, 利昌 イシイ, トシマサ

書誌事項

タイトル

Studies on multigraph connectivity augmentation problems

タイトル別名

多重グラフにおける連結度増大問題に関する研究

著者名

石井, 利昌

著者別名

イシイ, トシマサ

学位授与大学

京都大学

取得学位

博士 (情報学)

学位授与番号

甲第8483号

学位授与年月日

2000-03-23

注記・抄録

博士論文

目次

  1. 論文目録 / (0001.jp2)
  2. Contents / p5 (0008.jp2)
  3. 1 Introduction / p1 (0010.jp2)
  4. 1.1 Introduction / p1 (0010.jp2)
  5. 1.2 Basic definitions / p3 (0011.jp2)
  6. 1.3 Historical background / p5 (0012.jp2)
  7. 1.4 Structure of this thesis / p11 (0015.jp2)
  8. 2 Preliminaries / p13 (0016.jp2)
  9. 2.1 Definitions / p13 (0016.jp2)
  10. 2.2 Properties of k-Vertex-Connected Multigraphs / p14 (0017.jp2)
  11. 2.3 Edge-Splitting / p19 (0019.jp2)
  12. 2.4 Edge-Shifting / p25 (0022.jp2)
  13. 2.5 Lower Bounds on the Optimum Value of EVAP / p27 (0023.jp2)
  14. 3 Augmenting an Arbitrary Multigraph to an rλ-Edge-Connected and Biconnected Multigraph / p31 (0025.jp2)
  15. 3.1 Introduction / p31 (0025.jp2)
  16. 3.2 Lower bounds / p31 (0025.jp2)
  17. 3.3 Algorithm for EVAP(rλ,2) / p33 (0026.jp2)
  18. 3.4 Justification of Step I / p36 (0028.jp2)
  19. 3.5 Justification of Step II / p40 (0030.jp2)
  20. 3.6 Justification of Step III / p41 (0030.jp2)
  21. 3.7 Justification of Step IV / p43 (0031.jp2)
  22. 3.8 Case of EVAP(ℓ,2) / p46 (0033.jp2)
  23. 3.9 Preserving simplicity / p48 (0034.jp2)
  24. 3.10 Conclusion / p52 (0036.jp2)
  25. 4 Augmenting a Biconnected Multigraph to an ℓ-Edge-Connected and Triconnected Multigraph / p53 (0036.jp2)
  26. 4.1 Introduction / p53 (0036.jp2)
  27. 4.2 Lower bounds / p53 (0036.jp2)
  28. 4.3 Algorithm for EVAP(ℓ,3)in a Biconnected Multigraph / p55 (0037.jp2)
  29. 4.4 Justification of Step I / p62 (0041.jp2)
  30. 4.5 Justification of Step II / p70 (0045.jp2)
  31. 4.6 Justification of Step III / p70 (0045.jp2)
  32. 4.7 Justification of Step IV / p79 (0049.jp2)
  33. 4.8 Justification of Step V / p86 (0053.jp2)
  34. 4.9 Conclusion / p94 (0057.jp2)
  35. 5 Augmenting an Arbitrary Multigraph to an ℓ-Edge-Connected and Triconnected Multigraph / p95 (0057.jp2)
  36. 5.1 Introduction / p95 (0057.jp2)
  37. 5.2 Lower bounds / p97 (0058.jp2)
  38. 5.3 Algorithm for EVAP(ℓ,3) / p97 (0058.jp2)
  39. 5.4 Justification of Step I / p103 (0061.jp2)
  40. 5.5 Justification of Step II / p108 (0064.jp2)
  41. 5.6 Justification of Step III / p111 (0065.jp2)
  42. 5.7 Justification of Step IV / p113 (0066.jp2)
  43. 5.8 Conclusion / p114 (0067.jp2)
  44. 6 Augmenting a (k-ℓ)-Vertex-Connected Multigraph to an ℓ-Edge-Connected and k-Vertex-Connected Multigraph / p115 (0067.jp2)
  45. 6.1 Introduction / p115 (0067.jp2)
  46. 6.2 Lower bounds / p115 (0067.jp2)
  47. 6.3 Algorithm for EVAP(ℓ,k) / p117 (0068.jp2)
  48. 6.4 Justification of Step I / p120 (0070.jp2)
  49. 6.5 Justification of Step II / p121 (0070.jp2)
  50. 6.6 Complexity of Step III / p126 (0073.jp2)
  51. 6.7 Conclusion / p126 (0073.jp2)
  52. 7 Conclusion / p127 (0073.jp2)
1アクセス

各種コード

  • NII論文ID(NAID)
    500000188314
  • NII著者ID(NRID)
    • 8000000188597
  • DOI(NDL)
  • NDL書誌ID
    • 000000352628
  • データ提供元
    • NDL ONLINE
    • NDLデジタルコレクション
ページトップへ