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.
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]
Box-total dual integrality and edge-connectivity
M. BarbatoPrimo
;
2022
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.File | Dimensione | Formato | |
---|---|---|---|
boxTDI_MAPR_preprint.pdf
accesso aperto
Descrizione: Preprint (1a submission)
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
433.46 kB
Formato
Adobe PDF
|
433.46 kB | Adobe PDF | Visualizza/Apri |
boxTDI_MAPR_accepted.pdf
Open Access dal 01/02/2023
Descrizione: Manoscritto Accettato (2a submission)
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
388.46 kB
Formato
Adobe PDF
|
388.46 kB | Adobe PDF | Visualizza/Apri |
BoxTDI-MAPR_published.pdf
accesso riservato
Descrizione: Versione pubblicata ("Version of Record")
Tipologia:
Publisher's version/PDF
Dimensione
531.59 kB
Formato
Adobe PDF
|
531.59 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.