کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952423 | 1442031 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reducing rank of the adjacency matrix by graph modification
ترجمه فارسی عنوان
کاهش رتبه ماتریس مجاورت با تغییر گراف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F, of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F, we take algebraic route. More formally, given a fixed positive integer r, we define Fr as the family of graphs where for each GâFr, the rank of the adjacency matrix of G is at most r. Using the family Fr we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r-Rank Vertex Deletion, r-Rank Edge Deletion and r-Rank Editing. These problems generalize the classical Vertex Cover problem and a variant of the d-Cluster Editing problem. We first show that all the three problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2O(klogâ¡r)nO(1) for r-Rank Vertex Deletion, and an algorithm for r-Rank Edge Deletion and r-Rank Editing running in time 2O(f(r)klogâ¡k)nO(1). We complement our FPT result by designing polynomial kernels for these problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 70-79
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 70-79
نویسندگان
S.M. Meesum, Pranabendu Misra, Saket Saurabh,