Skip to Main Content (Press Enter)

Logo UNIMI
  • ×
  • Home
  • Persone
  • Attività
  • Ambiti
  • Strutture
  • Pubblicazioni
  • Terza Missione

Expertise & Skills
Logo UNIMI

|

Expertise & Skills

unimi.it
  • ×
  • Home
  • Persone
  • Attività
  • Ambiti
  • Strutture
  • Pubblicazioni
  • Terza Missione
  1. Pubblicazioni

Box-total dual integrality and edge-connectivity

Articolo
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
Autori di Ateneo:
BARBATO MICHELE ( autore )
Link alla scheda completa:
https://air.unimi.it/handle/2434/901454
Link al Full Text:
https://air.unimi.it/retrieve/handle/2434/901454/1964645/boxTDI_MAPR_preprint.pdf
https://air.unimi.it/retrieve/handle/2434/901454/1964646/boxTDI_MAPR_accepted.pdf
  • Aree Di Ricerca

Aree Di Ricerca

Settori


Settore MAT/09 - Ricerca Operativa
  • Informazioni
  • Assistenza
  • Accessibilità
  • Privacy
  • Utilizzo dei cookie
  • Note legali

Realizzato con VIVO | Progettato da Cineca | 26.1.3.0