文献

J-GLOBAL ID：202002281263170833   整理番号：20A2568616

高いバランスを持つハイパーグラフの多色彩色【JST・京大機械翻訳】

Polychromatic colorings of hypergraphs with high balance

著者 (3件)： Jiang Zhenzhen (School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, P. R. China) ,  Yue Jun (School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, P. R. China) ,  Zhang Xia (School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, P. R. China)
資料名： AIMS Mathematics (Web)  (AIMS Mathematics (Web))
巻： 5  号： 4  ページ： 3010-3018  発行年： 2020年 
JST資料番号： U7115A  ISSN： 2473-6988  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： mは正の整数であり,C={1,2,s,m}はm色の集合である。ハイパーグラフの多色性m彩色は,各ハイパーエッジがCにおける各色の少なくとも一つの頂点を含むような方法でその頂点の彩色である。この問題は,ハイパーグラフの2色化の一般化であり,無線センサネットワークのための最長寿命問題,超グラフのカバー分解問題,およびハイパーグラフの頂点カバー問題と密接な関係がある。本論文では,nハイパーエッジを持つハイパーグラフHが,各色が各ハイパーエッジ上で少なくともk時間に現れるような多色性m色付けを許す最大mを見つけることである。kが固定正整数であるとき,数に対する2lnn近似を得た。k=O(nlnn)の場合,O(lnn)近似アルゴリズムが存在する。k=ω(nlnn)の場合,(2+√3)k近似アルゴリズムが存在する。Copyright 2020 The Author(s) All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 近似法 ,  多色性 ,  着色 ,  *発色 ,  *超グラフ
準シソーラス用語： 無線センサネットワーク ,  近似アルゴリズム ,  確率的方法 , 【Automatic Indexing@JST】

著者キーワード (5件)： ハイパーグラフ ,  多色着色 ,  カバー分解 ,  平衡着色 ,  確率的方法

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

タイトルに関連する用語 (4件)： バランス ,  ハイパーグラフ ,  多色 ,  彩色