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. Barbato
Primo
;
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.
Box-total dual integrality; k-edge connected subgraph; Polyhedron; Series–parallel graph
Settore MAT/09 - Ricerca Operativa
2022
30-gen-2022
Article (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/901454
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact