کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420034 683889 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Resilience and optimization of identifiable bipartite graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Resilience and optimization of identifiable bipartite graphs
چکیده انگلیسی

A bipartite graph G=(L,R;E)G=(L,R;E) with at least one edge is said to be identifiable if for every vertex v∈Lv∈L, the subgraph induced by its non-neighbors has a matching of cardinality |L|−1|L|−1. This definition arises in the context of low-rank matrix factorization and is motivated by signal processing applications.In this paper, we study the resilience of identifiability with respect to edge additions, edge deletions and edge modifications. These can all be seen as measures of evaluating how strongly a bipartite graph possesses the identifiability property. On the one hand, we show that computing the resilience of this non-monotone property can be done in polynomial time for edge additions or edge modifications. On the other hand, for edge deletions this is an NP-complete problem. Our polynomial results are based on polynomial algorithms for computing the surplus of a bipartite graph GG and finding a tight set in GG, which might be of independent interest.We also deal with some complexity results for the optimization problem related to the isolation of a smallest set J⊆LJ⊆L that, together with all vertices with neighbors only in JJ, induces an identifiable subgraph. We obtain an APX-hardness result for the problem and identify some polynomially solvable cases.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 4–5, March 2013, Pages 593–603
نویسندگان
, , , ,