Show simple item record

Resilience and optimization of identifiable bipartite graphs

hal.structure.identifier
dc.contributor.authorRios-Solis, Yasmin Agueda*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553		*
hal.structure.identifier
dc.contributor.authorMilanic, Martin*
hal.structure.identifier
dc.contributor.authorFritzilas, Epameinondas*
dc.date.accessioned2012-06-18T09:16:31Z
dc.date.available2012-06-18T09:16:31Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9490
dc.language.isoenen
dc.subjectNP-complete problemen
dc.subjectIdentifiabilityen
dc.subjectResilienceen
dc.subjectMatchingen
dc.subjectBipartitegraphen
dc.subject.ddc511en
dc.titleResilience and optimization of identifiable bipartite graphsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherGraduate Program in Systems Engineering, Universidad Autónoma de Nuevo León (UANL;Mexique
dc.contributor.editoruniversityotherUP FAMNIT and UP IAM, University of Primorska;Slovénie
dc.contributor.editoruniversityotherFaculty of Technology, Bielefeld University;Allemagne
dc.description.abstractenA bipartite graph G=(L,R;E) with at least one edge 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 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 G and finding a tight set in G, 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⊆L that, together with all vertices with neighbors only in J, induces an identifiable subgraph. We obtain an APX-hardness result for the problem and identify some polynomially solvable cases.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol161
dc.relation.isversionofjnlissue4-5
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages593-603
dc.relation.isversionofdoi10.1016/j.dam.2012.01.005en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01508820*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record