Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs

DOI10.1137/S0895480190182691zbMath0802.05070OpenAlexW1980704718MaRDI QIDQ4307047

Francisco Barahona, Ali Ridha Mahjoub, Jean Fonlupt

Publication date: 1 December 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480190182691

zbMATH Keywords

inequalitiesminordirected graphfacetspolyhedral combinatoricsLucchesi-Younger theoremacyclic subgraph polytopecompositions of polyhedra

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the integral dicycle packings and covers and the linear ordering polytope, A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\), Ranking tournaments with no errors. II: Minimax relation, An updated survey on the linear ordering problem for weighted or unweighted tournaments, How to recycle your facets, Ranking tournaments with no errors. I: Structural description, Anti-forcing polynomials for benzenoid systems with forcing edges, Composition of graphs and the triangle-free subgraph polytope, Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs, Forcing matchings on square grids