• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Resilience and optimization of identifiable bipartite graphs

Rios-Solis, Yasmin Agueda; Monnot, Jérôme; Milanic, Martin; Fritzilas, Epameinondas (2013), Resilience and optimization of identifiable bipartite graphs, Discrete Applied Mathematics, 161, 4-5, p. 593-603. 10.1016/j.dam.2012.01.005

Type
Article accepté pour publication ou publié
Date
2013
Journal name
Discrete Applied Mathematics
Volume
161
Number
4-5
Publisher
Elsevier
Pages
593-603
Publication identifier
10.1016/j.dam.2012.01.005
Metadata
Show full item record
Author(s)
Rios-Solis, Yasmin Agueda

Monnot, Jérôme cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Milanic, Martin

Fritzilas, Epameinondas
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.
Subjects / Keywords
NP-complete problem; Identifiability; Resilience; Matching; Bipartitegraph

Related items

Showing items related by title and author.

  • Thumbnail
    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) Document de travail / Working paper
  • Thumbnail
    The exact weighted independent set problem in perfect graphs and related classes 
    Monnot, Jérôme; Milanic, Martin (2009) Article accepté pour publication ou publié
  • Thumbnail
    The complexity of the Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
  • Thumbnail
    The complexity of the Pk partition problem and related problems in bipartite graphs 
    Monnot, Jérôme; Toulouse, Sophie (2005) Communication / Conférence
  • Thumbnail
    Complexity and algorithms for constant diameter augmentation problems 
    Kim, Eun Jung; Milanic, Martin; Monnot, Jérôme; Picouleau, Christophe (2022) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo