Facets of the balanced (acyclic) induced subgraph polytope
From MaRDI portal
Publication:1122491
DOI10.1007/BF01589094zbMath0675.90071OpenAlexW1984619586MaRDI QIDQ1122491
Francisco Barahona, Ali Ridha Mahjoub
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 graphseries parallel graphfacets of polyhedrafacet defining inequalitiesacyclic induced subgraphsbalanced induced subgraph polytope
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)
Related Items
A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem, A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph, Separator-based data reduction for signed graph balancing, The minimum chromatic violation problem: a polyhedral approach, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Polyhedral results for the bipartite induced subgraph problem, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, An exact approach to the problem of extracting an embedded network matrix, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs, Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut, The maximum balanced subgraph of a signed graph: applications and solution approaches
Cites Work
- Polytope des independants d'un graphe série-parallèle
- On the notion of balance of a signed graph
- A Cutting Plane Algorithm for the Linear Ordering Problem
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
- On the facial structure of set packing polyhedra
