کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950583 | 1440713 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding connected k-subgraphs with high density
ترجمه فارسی عنوان
پیدا کردن کروماتوگرافی متصل با چگالی بالا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given an edge-weighted connected graph G on n vertices and a positive integer kâ¤n, a subgraph of G on k vertices is called a k-subgraph in G. We design combinatorial approximation algorithms for finding a connected k-subgraph in G such that its weighted density is at least a factor Ω(maxâ¡{1/k,k2/n2}) of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where maxâ¡{1/k,k2/n2}â¥nâ2/3 implies an O(n2/3)-approximation ratio. We obtain improved O(n2/5)-approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k-subgraph problem on general graphs. We also give O(nlogâ¡n)-approximation for the problem on general weighted interval graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 160-173
Journal: Information and Computation - Volume 256, October 2017, Pages 160-173
نویسندگان
Xujin Chen, Xiaodong Hu, Changjun Wang,