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

DOI10.1016/j.cor.2015.12.004zbMath1349.90819OpenAlexW2292659810MaRDI QIDQ342319

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 setsigned graphmaximum balanced induced subgraphnetwork matrixvertex frustration

Mathematics Subject Classification ID

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

Related Items (3)

Negative (and positive) circles in signed graphs: a problem collection ⋮ Negative circles in signed graphs: a problem collection ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review

Uses Software

• Mathematica
• CPLEX

Cites Work

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

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