Data di Pubblicazione:
2020
Citazione:
On k-edge-connected Polyhedra: Box-TDIness in Series-Parallel Graphs / M. Barbato, R. Grappe, M. Lacroix, E. Lancini (LECTURE NOTES IN COMPUTER SCIENCE). - In: Combinatorial Optimization / [a cura di] M. Baïou , B. Gendron, O. Günlük, A. Mahjoub. - [s.l] : Springer, 2020. - ISBN 9783030532611. - pp. 27-41 (( Intervento presentato al 6. convegno International Symposium on Combinatorial Optimization tenutosi a Montreal nel 2020 [10.1007/978-3-030-53262-8_3].
Abstract:
Given a connected graph G=(V,E) and an integer (formula presented), the connected graph H=(V,F) where F is a family of elements of E, is a k-edge-connected spanning subgraph of G if H remains connected after the removal of any k-1 edges. The convex hull of the k-edge-connected spanning subgraphs of a graph G forms the k-edge-connected spanning 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:
03 - Contributo in volume
Elenco autori:
M. Barbato, R. Grappe, M. Lacroix, E. Lancini
Link alla scheda completa:
Titolo del libro:
Combinatorial Optimization