Combinatorial properties and further facets of maximum edge subgraph polytopes

Mostrar todas las versiones(2)

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Marenco, J., Saban, D.
Formato:	JOUR
Materias:	Diameter of polytopes Facets Maximum edge subgraph problem
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_15710653_v37_nC_p303_Marenco
record_format	dspace
spelling	todo:paper_15710653_v37_nC_p303_Marenco2023-10-03T16:27:06Z Combinatorial properties and further facets of maximum edge subgraph polytopes Marenco, J. Saban, D. Diameter of polytopes Facets Maximum edge subgraph problem 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. Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Saban, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Diameter of polytopes Facets Maximum edge subgraph problem
spellingShingle	Diameter of polytopes Facets Maximum edge subgraph problem Marenco, J. Saban, D. Combinatorial properties and further facets of maximum edge subgraph polytopes
topic_facet	Diameter of polytopes Facets Maximum edge subgraph problem
description	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.
format	JOUR
author	Marenco, J. Saban, D.
author_facet	Marenco, J. Saban, D.
author_sort	Marenco, J.
title	Combinatorial properties and further facets of maximum edge subgraph polytopes
title_short	Combinatorial properties and further facets of maximum edge subgraph polytopes
title_full	Combinatorial properties and further facets of maximum edge subgraph polytopes
title_fullStr	Combinatorial properties and further facets of maximum edge subgraph polytopes
title_full_unstemmed	Combinatorial properties and further facets of maximum edge subgraph polytopes
title_sort	combinatorial properties and further facets of maximum edge subgraph polytopes
url	http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p303_Marenco
work_keys_str_mv	AT marencoj combinatorialpropertiesandfurtherfacetsofmaximumedgesubgraphpolytopes AT saband combinatorialpropertiesandfurtherfacetsofmaximumedgesubgraphpolytopes
_version_	1807323372980273152

Combinatorial properties and further facets of maximum edge subgraph polytopes

Ejemplares similares