社会的距離に基づく木の最適分割

• Item type: SIG Technical Reports(1)
• 公開日: 2018-05-18
• タイトル: 社会的距離に基づく木の最適分割
• タイトル / 言語: en
• タイトル: Optimal partition of a tree with social distance
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学大学院情報学研究科数理情報学専攻
• 著者所属: 中央大学理工学部情報工学科
• 著者所属: 名古屋大学大学院情報学研究科数理情報学専攻
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University, Department of Information and System Engineering, Chuo University,
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Nagoya University
• 著者名: 大久保, 壮浩; 土中, 哲秀; 小野, 廣隆
• 著者名(英): Masahiro, Okubo; Tesshu, Hanaka; Hirotaka, Ono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 与えられた単純無向グラフ G = (V，E) の頂点集合 V の分割 {C₁，C₂,...,Ck} をグラフ分割という．グラフ G における頂点間の距離に基づき分割の社会的効用を定義し，これを評価尺度としたグラフ分割をグラフの最適社会効用分割と呼ぶ．一般に，グラフが与えられたときその最適社会効用分割を求めることは NP 困難である．本論文では，対象とするグラフを木に限定した場合，O (△²n) 時間で最適社会効用分割が得られることを示す．ただし，n は頂点数，△ は最大次数である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given a graph G = (V,E), a partition {Ci, G2,...,Ck} of V is called a graph partition. We consider a social welfare of a graph partition of G based on distances between vertices in G, and define a graph partition with optimal social welfare. Finding a graph partition with optimal social welfare is known to be NP-hard in general. In this paper, we show that a graph partition with optimal social welfare of a given tree can be computed in O (△²n) time, where n is the number of vertices and △ is the maximum degree.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-168, 号 6, p. 1-8, 発行日 2018-05-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会