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

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

Articolo
Data di Pubblicazione:
2022
Citazione:
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]
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).
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Box-total dual integrality; Flow cone; Hilbert basis; Multicuts; Schrijver system; Series–parallel graphs; Total dual integrality
Elenco autori:
M. Barbato, R. Grappe, M. Lacroix, E. Lancini, R. Wolfler Calvo
Autori di Ateneo:
BARBATO MICHELE ( autore )
Link alla scheda completa:
https://air.unimi.it/handle/2434/781837
  • 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