A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem

DOI10.1016/J.COR.2015.12.004MaRDI QIDQ342319zbMATH OpenOpenAlexFDO

Authors Fabrizio Marinelli, Angelo Parente

Publication date 17 November 2016

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2015.12.004

zbMATH Keywords

independent setmaximum balanced induced subgraphnetwork matrixsigned graphvertex frustration

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A matheuristic approach for the maximum balanced subgraph of a signed graph
• The maximum balanced subgraph of a signed graph: applications and solution approaches
• scientific article; zbMATH DE number 1472163
• A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph
• Maximum balanced subgraph problem parameterized above lower bound

Cites work

• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• A branch-and-cut algorithm for the maximum cardinality stable set problem
• A decomposition theory for matroids. V: Testing of matrix total unimodularity
• An exact approach to the problem of extracting an embedded network matrix
• Automatic identification of embedded network rows in large-scale optimization models
• Conflict graphs in solving integer programming problems
• Converting Linear Programs to Network Problems
• Detecting embedded networks in LP using GUB structures and independent set algorithms
• Erratum to: T. Zaslavsky, signed graphs
• Extracting pure network submatrices in linear programs using signed graphs.
• Facets of the balanced (acyclic) induced subgraph polytope
• Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics
• Fixed-parameter algorithms in analysis of heuristics for extracting networks in linear programs
• Graph Bipartization and via minimization
• Graph theory
• Handbook on modelling for discrete optimization.
• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 3121294 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 1339492 (Why is no real title available?)
• On the notion of balance of a signed graph
• Separator-based data reduction for signed graph balancing
• Set packing relaxations of some integer programs
• Signed graphs
• Signed graphs for portfolio analysis in risk management
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Strong lift-and-project cutting planes for the stable set problem
• Vertex cover: Further observations and further improvements

Cited in

(5)

• Negative (and positive) circles in signed graphs: a problem collection
• The maximum balanced subgraph of a signed graph: applications and solution approaches
• Negative circles in signed graphs: a problem collection
• A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph
• Maximum weighted induced forests and trees: new formulations and a computational comparative review

Describes a project that uses

Uses Software

• Mathematica
• CPLEX

This page was built for publication: A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342319)