کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477686 | 1446178 | 2008 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs](/preview/png/477686.png)
چکیده انگلیسی
Multicut is a fundamental network communication and connectivity problem. It is defined as: given an undirected graph and a collection of pairs of terminal vertices, find a minimum set of edges or vertices whose removal disconnects each pair. We mainly focus on the case of removing vertices, where we distinguish between allowing or disallowing the removal of terminal vertices. Complementing and refining previous results from the literature, we provide several NP-completeness and (fixed-parameter) tractability results for restricted classes of graphs such as trees, interval graphs, and graphs of bounded treewidth.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 186, Issue 2, 16 April 2008, Pages 542–553
Journal: European Journal of Operational Research - Volume 186, Issue 2, 16 April 2008, Pages 542–553
نویسندگان
Jiong Guo, Falk Hüffner, Erhan Kenar, Rolf Niedermeier, Johannes Uhlmann,