We represent a flow of a graph G=(V,E) as a couple (C,e) with C a circuit of G and e an edge of C, and its incidence vector is the 0∕±1 vector χC∖e−χe. The flow cone of G is the cone generated by the flows of G and the unit vectors. When G has no K5-minor, this cone can be described by the system x(M)≥0 for all multicuts M of G. We prove that this system is box-totally dual integral if and only if G is series–parallel. Then, we refine this result to provide the Schrijver system describing the flow cone in series–parallel graphs. This answers a question raised by Chervet et al., (2018).

The Schrijver system of the flow cone in series–parallel graphs / M. Barbato, R. Grappe, M. Lacroix, E. Lancini, R. Wolfler Calvo. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 308:(2022 Feb 15), pp. 162-167. [10.1016/j.dam.2020.03.054]

The Schrijver system of the flow cone in series–parallel graphs

M. Barbato
Primo
;
2022

Abstract

We represent a flow of a graph G=(V,E) as a couple (C,e) with C a circuit of G and e an edge of C, and its incidence vector is the 0∕±1 vector χC∖e−χe. The flow cone of G is the cone generated by the flows of G and the unit vectors. When G has no K5-minor, this cone can be described by the system x(M)≥0 for all multicuts M of G. We prove that this system is box-totally dual integral if and only if G is series–parallel. Then, we refine this result to provide the Schrijver system describing the flow cone in series–parallel graphs. This answers a question raised by Chervet et al., (2018).
Box-total dual integrality; Flow cone; Hilbert basis; Multicuts; Schrijver system; Series–parallel graphs; Total dual integrality
Settore MAT/09 - Ricerca Operativa
15-feb-2022
17-apr-2020
Article (author)
File in questo prodotto:
File Dimensione Formato  
schrijver_flowcone_spgraph_dam.pdf

accesso riservato

Descrizione: Articolo principale. Publisher's version apparsa on-line in attesa della stampa
Tipologia: Publisher's version/PDF
Dimensione 314.91 kB
Formato Adobe PDF
314.91 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
articolo_DAM_flowcone.pdf

accesso riservato

Descrizione: Articolo principale
Tipologia: Publisher's version/PDF
Dimensione 403.42 kB
Formato Adobe PDF
403.42 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/781837
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 2
social impact