The Schrijver system of the flow cone in series–parallel graphs
| Autor: | Michele Barbato, Roberto Wolfler Calvo, Roland Grappe, Emiliano Lancini, Mathieu Lacroix |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Combinatorics
010201 computation theory & mathematics Unit vector Applied Mathematics 0211 other engineering and technologies Discrete Mathematics and Combinatorics 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Series and parallel circuits 01 natural sciences Graph Mathematics |
| Zdroj: | Discrete Applied Mathematics. 308:162-167 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2020.03.054 |
| Popis: | 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 K 5 -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). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect