与えられた次数列を連結度最大のグラフで実現するO（n log log n）時間アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1993-11-25
• タイトル: 与えられた次数列を連結度最大のグラフで実現するO（n log log n）時間アルゴリズム
• タイトル / 言語: en
• タイトル: An O (n log log n) Time Algorithm for Constructing a Graph of Maximum Connectivity with Prescribed Degrees
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 中央大学理工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering Chuo University
• 著者名: 浅野, 孝夫
• 著者名(英): Takao, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 非負整数の列D=（_1，d_2，…，d_）を実現するグラフが存在するとき、Dをグラフ次数列という。グラフ次数列Dに対して、Dを実現するk?連結グラフは存在するが、（+）?連結グラフは存在しないとき、Dの連結度κ（）はkであるという。本論文では、与えられたグラフ次数列Dに対して、Dをκ（）?連結グラフで実現するO（ log log ）の手間のアルゴリズムを与える。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A sequence of nonnegative integers D = (d_1,d_2,…,d_n) is graphical if there is a graph with degree sequence D. The connectivity κ(D) of graphical sequence D is defined to be the maximum integer k such that there is k-connected graph with degree sequence. D In this paper, we present an O(n log log n) time algorithm, for a given graphical sequence D. to construct a κ(D)-connected graph with degree sequence D.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 104(1993-AL-036), p. 33-40, 発行日 1993-11-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会