Combinatorial properties and further facets of maximum edge subgraph polytopes
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) a...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2011
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 03903caa a22004337a 4500 | ||
|---|---|---|---|
| 001 | PAPER-10381 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204025.0 | ||
| 008 | 190411s2011 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-80053086565 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Marenco, J. | |
| 245 | 1 | 0 | |a Combinatorial properties and further facets of maximum edge subgraph polytopes |
| 260 | |c 2011 | ||
| 270 | 1 | 0 | |m Marenco, J.; Sciences Institute, National University of General SarmientoArgentina; email: jmarenco@ungs.edu.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T., Greedily Finding Dense Subgraphs (2000) Journal of Algorithms, 34, pp. 203-221 | ||
| 504 | |a Asahiro, Y., Hassin, R., Iwama, K., Complexity of finding dense subgraphs (2002) Discrete Applied Mathematics, 121, pp. 15-26 | ||
| 504 | |a Billionnet, A., Different formulations for solving the heaviest k-subgraph problem (2005) Information Systems and Operational Research, 43 (3), pp. 171-186 | ||
| 504 | |a Feige, U., Kortsarz, G., Peleg, D., The Dense k-Subgraph Problem (2001) Algorithmica, 29, pp. 410-421 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a Bonomo, F., Marenco, J., Saban, D., Stier-Moses, N., A polyhedral study of the maximum edge subgraph problem, Submitted to Discrete Applied Mathematics | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Sciences Institute, National University of General Sarmiento, Argentina | ||
| 593 | |a Computer Science Dept., FCEN, University of Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a DIAMETER OF POLYTOPES |
| 690 | 1 | 0 | |a FACETS |
| 690 | 1 | 0 | |a MAXIMUM EDGE SUBGRAPH PROBLEM |
| 700 | 1 | |a Saban, D. | |
| 773 | 0 | |d 2011 |g v. 37 |h pp. 303-308 |k n. C |p Electron. Notes Discrete Math. |x 15710653 |t Electronic Notes in Discrete Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-80053086565&doi=10.1016%2fj.endm.2011.05.052&partnerID=40&md5=b5eaa75669be6ce8398cf80fff9a690b |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.endm.2011.05.052 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p303_Marenco |y Registro en la Biblioteca Digital |
| 961 | |a paper_15710653_v37_nC_p303_Marenco |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 71334 | ||