Resilience and optimization of identifiable bipartite graphs

Fritzilas E, Milanic M, Monnot J, Rios-Solis YA (2013)
Discrete Applied Mathematics 161(4-5): 593-603.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Fritzilas, Epameinondas; Milanic, Martin; Monnot, Jerome; Rios-Solis, Yasmin A.
Abstract / Bemerkung
A bipartite graph G = (L, R; E) with at least one edge is said to be identifiable if for every vertex v is an element of L, the subgraph induced by its non-neighbors has a matching of cardinality vertical bar L vertical bar - 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 subset of L that, together with all vertices with neighbors only in], induces an identifiable subgraph. We obtain an APX-hardness result for the problem and identify some polynomially solvable cases. (C) 2012 Elsevier B.V. All rights reserved.
Stichworte
Bipartite graph; Resilience; Identifiability; Matching
Erscheinungsjahr
2013
Zeitschriftentitel
Discrete Applied Mathematics
Band
161
Ausgabe
4-5
Seite(n)
593-603
ISSN
0166-218X
Page URI
https://pub.uni-bielefeld.de/record/2565296

Zitieren

Fritzilas E, Milanic M, Monnot J, Rios-Solis YA. Resilience and optimization of identifiable bipartite graphs. Discrete Applied Mathematics. 2013;161(4-5):593-603.
Fritzilas, E., Milanic, M., Monnot, J., & Rios-Solis, Y. A. (2013). Resilience and optimization of identifiable bipartite graphs. Discrete Applied Mathematics, 161(4-5), 593-603. doi:10.1016/j.dam.2012.01.005
Fritzilas, Epameinondas, Milanic, Martin, Monnot, Jerome, and Rios-Solis, Yasmin A. 2013. “Resilience and optimization of identifiable bipartite graphs”. Discrete Applied Mathematics 161 (4-5): 593-603.
Fritzilas, E., Milanic, M., Monnot, J., and Rios-Solis, Y. A. (2013). Resilience and optimization of identifiable bipartite graphs. Discrete Applied Mathematics 161, 593-603.
Fritzilas, E., et al., 2013. Resilience and optimization of identifiable bipartite graphs. Discrete Applied Mathematics, 161(4-5), p 593-603.
E. Fritzilas, et al., “Resilience and optimization of identifiable bipartite graphs”, Discrete Applied Mathematics, vol. 161, 2013, pp. 593-603.
Fritzilas, E., Milanic, M., Monnot, J., Rios-Solis, Y.A.: Resilience and optimization of identifiable bipartite graphs. Discrete Applied Mathematics. 161, 593-603 (2013).
Fritzilas, Epameinondas, Milanic, Martin, Monnot, Jerome, and Rios-Solis, Yasmin A. “Resilience and optimization of identifiable bipartite graphs”. Discrete Applied Mathematics 161.4-5 (2013): 593-603.
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Suchen in

Google Scholar