Data di Pubblicazione:
2022
Citazione:
Box-total dual integrality and edge-connectivity / M. Barbato, R. Grappe, M. Lacroix, E. Lancini. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - (2022). [Epub ahead of print] [10.1007/s10107-021-01743-x]
Abstract:
Given a graph G = (V, E) and an integer k >= 1, the graph H = (V, F), where F is a family of elements (with repetitions allowed) of E, is a k-edge-connected spanning subgraph of G if H cannot be disconnected by deleting any k - 1 elements of F. The convex hull of incidence vectors of the k-edge-connected subgraphs of a graph G forms the k-edge-connected subgraph polyhedron of G. We prove that this polyhedron is box-totally dual integral if and only if G is series-parallel. In this case, we also provide an integer box-totally dual integral system describing this polyhedron.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Box-total dual integrality; k-edge connected subgraph; Polyhedron; Series–parallel graph
Elenco autori:
M. Barbato, R. Grappe, M. Lacroix, E. Lancini
Link alla scheda completa: