Maximum balanced subgraph problem parameterized above lower bound

DOI10.1016/J.TCS.2013.10.026MaRDI QIDQ391973zbMATH OpenOpenAlexFDO

Authors Robert Crowston, G. Gutin, M. Jones, Gabriele Muciaccia

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.10.026

zbMATH Keywords

balanced subgraphfixed parameter tractablekernelsigned graph

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Maximum balanced subgraph problem parameterized above lower bound
• scientific article; zbMATH DE number 6987353
• A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph
• A matheuristic approach for the maximum balanced subgraph of a signed graph
• Optimal Edge Deletions for Signed Graph Balancing

Cites work

• A mathematical bibliography of signed and gain graphs and allied areas
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Beyond Max-Cut: -extendible properties parameterized above the Poljak-Turzík bound
• Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound
• Extracting pure network submatrices in linear programs using signed graphs.
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Max-Cut parameterized above the Edwards-Erdős bound
• Note on maximal bisection above tight lower bound
• On the notion of balance of a signed graph
• Optimal Edge Deletions for Signed Graph Balancing
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below guaranteed values
• Parametrized complexity theory.
• Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average

Cited in

(10)

• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• Parameterized complexity of multi-node hubs
• Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
• A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph
• Maximum balanced subgraph problem parameterized above lower bound
• A matheuristic approach for the maximum balanced subgraph of a signed graph
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• Optimal Edge Deletions for Signed Graph Balancing
• Separator-based data reduction for signed graph balancing
• Linear kernels and linear-time algorithms for finding large cuts

This page was built for publication: Maximum balanced subgraph problem parameterized above lower bound

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