グラフ次数列問題

• Item type: SIG Technical Reports(1)
• 公開日: 1993-05-28
• タイトル: グラフ次数列問題
• タイトル / 言語: en
• タイトル: Graphical Degree Sequence Problems
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 愛知技術短期大学電子工学科
• 著者所属: 中央大学理工学部情報工学科
• 著者所属: 中央大学理工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Electronic Engineering, Aichi College of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering
• 著者名: 高橋, 昌也; 今井, 桂子; 浅野, 孝夫
• 著者名(英): Masaya, Takahashi; Keiko, Imai; Takao, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 非負整数の列S=（_1，s_2，…，s_）がグラフ的であるとは、それを次数列としてもつようなグラフが存在することであり、グラフ次数列問題とは、与えられた非負整数列S=（_1，s_2，…，s_）に対して、Sがグラフ的であるかどうかを判定し、もしそうならば、Sを次数列としてもつグラフを構成する問題である。本論文では、各種のグラフ次数列問題を考え、効率的アルゴリズムを与える。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A sequence of nonnegative integers S=(s_1,s_2,…,s_n) is graphical if there is a graph with vertices υ_1,υ_2,…,υ_n such that deg(υ_i) = s_i for each i = 1,2,…,n. The graphical degree sequence problem is: Given a sequence S of nonnegative integers, determine whether it is graphical and, if so, construct a graph having S as a degree sequence. In this paper, we consider several variations of the graphical degree sequence problem and give efficient algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 48(1993-AL-033), p. 111-118, 発行日 1993-05-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会