Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs

DOI10.1137/S0895480190182666zbMath0802.05067MaRDI QIDQ4307044

Francisco Barahona, Ali Ridha Mahjoub

Publication date: 1 December 1994

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

zbMATH Keywords

algorithminequalitiesseries-parallel graphspolyhedral combinatoricsbalanced subgraphscomposition of polyhedraacyclic subgraphscompact systemssubgraph polytope

Mathematics Subject Classification ID

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

Related Items

On the feedback vertex set polytope of a series-parallel graph, Facets of the balanced (acyclic) induced subgraph polytope, The minimum chromatic violation problem: a polyhedral approach, Graph Bipartization Problem with Applications to Via Minimization in VLSI Design, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Polyhedral results for the bipartite induced subgraph problem, Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus, Cutting planes from extended LP formulations, Compositions in the bipartite subgraph polytope, On cuts and matchings in planar graphs, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs