کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4968293 | 1449571 | 2016 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A parallel min-cut algorithm using iteratively reweighted least squares targeting at problems with floating-point edge weights
ترجمه فارسی عنوان
یک الگوریتم مینی برش موازی با استفاده از مقادیر کمترین مربعات تکراری که در مسائل با وزن لبه های شناور نقطه هدف قرار می گیرند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نرم افزارهای علوم کامپیوتر
چکیده انگلیسی
We present a parallel algorithm for the undirected s-t min-cut problem with floating-point valued edge weights. Our overarching algorithm uses an iteratively reweighted least squares framework. Specifically, this algorithm generates a sequence of Laplacian linear systems, which are solved in parallel. The iterative nature of our algorithm enables us to trade off solution quality for execution time, which is distinguished from those purely combinatorial algorithms that only produce solutions at optimum. We also propose a novel two-level rounding procedure that helps to enhance the quality of the approximate min-cut solution output by our algorithm. Our overall implementation, including the rounding procedure, demonstrates significant speed improvement over a state-of-the-art serial solver, where it could be up to 200 times faster on commodity platforms.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Parallel Computing - Volume 59, November 2016, Pages 43-59
Journal: Parallel Computing - Volume 59, November 2016, Pages 43-59
نویسندگان
Yao Zhu, David F. Gleich,