کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777226 1632576 2016 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On Minimum Average Stretch Spanning Trees in Grid Graphs
ترجمه فارسی عنوان
در حداقل میانگین درختان کشش کششی در نمودارهای گرید
کلمات کلیدی
حداقل دراز درخت درختی دراز کششی، نمودارهای شبکه،
ترجمه چکیده
حداقل دره درختی از یک درخت درختی که در آن قرار دارد، یک درخت پوشا است که کشش متوسط ​​را به حداقل می رساند. ما یک شرایط لازم و کافی برای یک درخت درختی را به عنوان حداقل دره درخت درخت (کشش) در نمودارهای شبکه ارائه می دهیم و یک الگوریتم زمان خطی برای ساخت ماست ارائه می دهیم.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش مقاله
در حداقل میانگین درختان کشش کششی در نمودارهای گرید
چکیده انگلیسی
A minimum average stretch spanning tree of a graph is a spanning tree that minimizes the average stretch. We present a necessary-and-sufficient condition for a spanning tree to be a minimum average stretch spanning tree (mast) in grid graphs and provide a linear-time algorithm to construct an mast.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 55, November 2016, Pages 131-134
نویسندگان
, ,