Show simple item record

dc.contributor.authorFritzilas, Epameinondas
dc.contributor.authorMilanic, Martin
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorRios-Solis, Yasmin Agueda
dc.date.accessioned2010-06-26T12:45:25Z
dc.date.available2010-06-26T12:45:25Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/4439
dc.language.isoenen
dc.subjectsource-sensor networken
dc.subjectcombinatorial optimizationen
dc.subjectcomplexityen
dc.subjectbipartite matchingen
dc.subject.ddc003en
dc.titleA matching-related property of bipartite graphs with applications in signal processingen
dc.typeDocument de travail / Working paper
dc.description.abstractenA 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.en
dc.publisher.nameUniversité Paris-Dauphineen
dc.publisher.cityParisen
dc.identifier.citationpages22en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record