A matching-related property of bipartite graphs with applications in signal processing
Fritzilas, Epameinondas; Milanic, Martin; Monnot, Jérôme; Rios-Solis, Yasmin Agueda (2009), A matching-related property of bipartite graphs with applications in signal processing. https://basepub.dauphine.fr/handle/123456789/4439
TypeDocument de travail / Working paper
MetadataShow full item record
Abstract (EN)A bipartite graph G = (L,R;E) is said to be identifiable if for every vertex v ∈ L, the subgraph induced by its non-neighbors has a matching of cardinality |L| − 1. This definition arises in the context of low-rank matrix factorization. Motivated by signal processing applications, in this paper we (i) propose the robustness of identifiability with respect to edge modifications as a polynomially computable measure of evaluating how strongly a bipartite graph possesses the property of identifiability, and (ii) introduce three problems that deal with finding identifiable subgraphs, and study their complexity.
Subjects / Keywordssource-sensor network; combinatorial optimization; complexity; bipartite matching
Showing items related by title and author.