Facets of the balanced (acyclic) induced subgraph polytope
DOI10.1007/BF01589094zbMATH Open0675.90071OpenAlexW1984619586MaRDI QIDQ1122491FDOQ1122491
A. R. Mahjoub, Francisco Barahona
Publication date: 1989
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01589094
signed graphfacets of polyhedraseries parallel graphfacet defining inequalitiesacyclic induced subgraphsbalanced induced subgraph polytope
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)
Cites Work
- On the notion of balance of a signed graph
- On the facial structure of set packing polyhedra
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
- Polytope des independants d'un graphe série-parallèle
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
Cited In (11)
- Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- The maximum balanced subgraph of a signed graph: applications and solution approaches
- A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem
- Solving VLSI design and DNA sequencing problems using bipartization of graphs
- Polyhedral results for the bipartite induced subgraph problem
- Separator-based data reduction for signed graph balancing
- A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph
- An exact approach to the problem of extracting an embedded network matrix
- The minimum chromatic violation problem: a polyhedral approach
- Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
This page was built for publication: Facets of the balanced (acyclic) induced subgraph polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122491)
