文献

J-GLOBAL ID：201702296124718415   整理番号：17A1965620

さまざまな費用関数のもとにおけるミニマックス全域木問題の改良【Powered by NICT】

Upgrading min-max spanning tree problem under various cost functions

著者 (2件)： Sepasian Ali Reza (Department of Mathematics, Fasa University, Fasa, Iran) ,  Monabbati Ehsan (Department of Mathematics, Alzahra University, Tehran, Iran)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 704  ページ： 87-91  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 向上ミニマックススパンニング木問題(MMST)検討した。グラフG(V , E)を考慮するなら,この問題の目的は,ある種の限界と与えられた予算下でのエッジ重みを修正することである摂動グラフに関してMMSTを可能な限り改善するようにした。一般非減少費用関数のための複雑性結果を提示した。特別な場合では,線形および和形式Hamming費用関数下で問題がO(| E | ~2)とO(E logE log V)時間で解決できることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *スパンニング木 ,  線形性 ,  グラフ ,  摂動 ,  *費用関数
準シソーラス用語： 複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： 位置問題 ,  問題改良 ,  ミニマックススパンニング木

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

タイトルに関連する用語 (3件)： 費用関数 ,  全域木 ,  問題