Artículo
Abstract:
Given a graph G and an integer k, the maximum edge subgraph problem consists in finding a k-vertex subset of G such that the number of edges within the subset is maximum. This NP-hard problem arises in the analysis of cohesive subgroups in social networks. In this work we study the polytope P(G,k) associated with a straightforward integer programming formulation of the maximum edge subgraph problem. We characterize the graph generated by P(G,k) and give a tight bound on its diameter. We give a complete description of P(K1n,k), where K1n is the star on n+1 vertices, and we conjecture a complete description of P(mK2,k), where mK2 is the graph composed by m disjoint edges. Finally, we introduce three families of facet-inducing inequalities for P(G,k), which generalize known families of valid inequalities for this polytope. © 2011 Elsevier B.V.
Registro:
| Documento: | Artículo |
| Título: | Combinatorial properties and further facets of maximum edge subgraph polytopes |
| Autor: | Marenco, J.; Saban, D. |
| Filiación: | Sciences Institute, National University of General Sarmiento, Argentina Computer Science Dept., FCEN, University of Buenos Aires, Argentina |
| Palabras clave: | Diameter of polytopes; Facets; Maximum edge subgraph problem |
| Año: | 2011 |
| Volumen: | 37 |
| Número: | C |
| Página de inicio: | 303 |
| Página de fin: | 308 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2011.05.052 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p303_Marenco |
Referencias:
- Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T., Greedily Finding Dense Subgraphs (2000) Journal of Algorithms, 34, pp. 203-221
- Asahiro, Y., Hassin, R., Iwama, K., Complexity of finding dense subgraphs (2002) Discrete Applied Mathematics, 121, pp. 15-26
- Billionnet, A., Different formulations for solving the heaviest k-subgraph problem (2005) Information Systems and Operational Research, 43 (3), pp. 171-186
- Feige, U., Kortsarz, G., Peleg, D., The Dense k-Subgraph Problem (2001) Algorithmica, 29, pp. 410-421
- Han, Q., Ye, T., Zhang, J., Approximation of Dense-k-Subgraph, Working Paper, Department of Management Sciences (2000), Henry B. Tippie College of Business, The University of Iowa; Roupin, F., Billionnet, A., A deterministic approximation algorithm for the Densest k-Subgraph Problem (2008) International Journal of Operational Research, 3 (3), pp. 301-314
- Bonomo, F., Marenco, J., Saban, D., Stier-Moses, N., A polyhedral study of the maximum edge subgraph problem (2009) Electronic Notes in Discrete Mathematics, 35, pp. 197-202
- Bonomo, F., Marenco, J., Saban, D., Stier-Moses, N., A polyhedral study of the maximum edge subgraph problem, Submitted to Discrete Applied Mathematics
Citas:
---------- APA ----------
Marenco, J. & Saban, D. (2011) . Combinatorial properties and further facets of maximum edge subgraph polytopes. Electronic Notes in Discrete Mathematics, 37(C), 303-308.http://dx.doi.org/10.1016/j.endm.2011.05.052
---------- CHICAGO ----------
Marenco, J., Saban, D. "Combinatorial properties and further facets of maximum edge subgraph polytopes" . Electronic Notes in Discrete Mathematics 37, no. C (2011) : 303-308.http://dx.doi.org/10.1016/j.endm.2011.05.052
---------- MLA ----------
Marenco, J., Saban, D. "Combinatorial properties and further facets of maximum edge subgraph polytopes" . Electronic Notes in Discrete Mathematics, vol. 37, no. C, 2011, pp. 303-308.http://dx.doi.org/10.1016/j.endm.2011.05.052
---------- VANCOUVER ----------
Marenco, J., Saban, D. Combinatorial properties and further facets of maximum edge subgraph polytopes. Electron. Notes Discrete Math. 2011;37(C):303-308.http://dx.doi.org/10.1016/j.endm.2011.05.052
