• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Resilience and optimization of identifiable bipartite graphs

Thumbnail
Date
2013
Dewey
Principes généraux des mathématiques
Sujet
NP-complete problem; Identifiability; Resilience; Matching; Bipartitegraph
Journal issue
Discrete Applied Mathematics
Volume
161
Number
4-5
Publication date
2013
Article pages
593-603
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2012.01.005
URI
https://basepub.dauphine.fr/handle/123456789/9490
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Rios-Solis, Yasmin Agueda
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Milanic, Martin
Fritzilas, Epameinondas
Type
Article accepté pour publication ou publié
Abstract (EN)
A 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.