文献

J-GLOBAL ID：202202216569539371   整理番号：22A0564054

低縮退を持つグラフへの等価分割縮退グラフの高速アルゴリズム【JST・京大機械翻訳】

Fast algorithm of equitably partitioning degenerate graphs into graphs with lower degeneracy

著者 (4件)： Zhang Xin (School of Mathematics and Statistics, Xidian University, Xi’an, 710071, China) ,  Zhang Huaqiang (School of Mathematics and Statistics, Xidian University, Xi’an, 710071, China) ,  Niu Bei (School of Mathematics and Statistics, Xidian University, Xi’an, 710071, China) ,  Li Bi (School of Mathematics and Statistics, Xidian University, Xi’an, 710071, China)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 905  ページ： 18-30  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGのq-縮退k-分割は,V(G)=∪i=1kViと各Viがq縮退部分グラフを誘発するようなV(G)のkペアワイズ分離サブセットの収集(V1,V2,...,Vk)である。このような分割は,1≦i<j≦kごとに||V_i|-|V_j|>1のとき,等値と呼ばれる。グラフの公正な分割は,いくつかの基本原理に基づくより小さなサブモジュールに大きいネットワークを分割する問題をモデル化して,ネットワーク科学と情報科学において多くの他の応用を持っている。本研究では,低縮退のグラフに縮退グラフを等しく分割する理論的およびアルゴリズム的結果を確立した。特に,ほとんどのn/βでの最大次数を有するあらゆるn-頂点d-縮退グラフは,q,α,およびβが明確な不等式を満たすとき,各k≧α_dに対してq-縮退k-分割(V_1,V_2,...,V_k)を持ち,そのような分割は立方時間で計算できることを示した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  *グラフ ,  不等式 ,  情報科学 ,  ネットワーク ,  *高速アルゴリズム ,  部分グラフ ,  問題 ,  *縮退 ,  部分集合 ,  頂点
準シソーラス用語： ネットワーク科学 , 【Automatic Indexing@JST】

著者キーワード (5件)： ネットワーク分割 ,  公平な着色 ,  樹木着色 ,  縮退グラフ ,  立方時間アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 縮退 ,  グラフ ,  等価 ,  高速アルゴリズム