کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419347 | 683788 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial-time algorithms for special cases of the maximum confluent flow problem
ترجمه فارسی عنوان
الگوریتم های چندجملهای زمان برای موارد خاصی از مساله جریان حداکثر وابستگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A flow on a directed network is said to be confluent if the flow uses at most one outgoing arc at each node. Confluent flows arise naturally in destination-based routing. We study the maximum confluent flow problem (MaxConf) with a single commodity but multiple sources and sinks and heterogeneous arc capacities. It was recently shown that MaxConf is NPNP-hard even on trees. We improve the classification of easy and hard confluent flow problems by providing polynomial-time algorithms for outerplanar graphs with a single sink, as well as trees with a constant number of either sources or sinks. Furthermore, we present an FPTAS for graphs with bounded treewidth.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 163, Part 2, 30 January 2014, Pages 142–154
Journal: Discrete Applied Mathematics - Volume 163, Part 2, 30 January 2014, Pages 142–154
نویسندگان
Daniel Dressler, Martin Strehler,