Separator-based data reduction for signed graph balancing
From MaRDI portal
Publication:613659
DOI10.1007/S10878-009-9212-2zbMATH Open1206.90201OpenAlexW2030737920MaRDI QIDQ613659FDOQ613659
Authors: Falk Hüffner, Nadja Betzler, Rolf Niedermeier 
Publication date: 21 December 2010
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-009-9212-2
Recommendations
exact algorithmpreprocessingalgorithm engineeringfinancial networkparameterized algorithmicsgene-regulatory network
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- A mathematical bibliography of signed and gain graphs and allied areas
- Mining market data: a network approach
- On the notion of balance of a signed graph
- Finding odd cycle transversals.
- Parametrized complexity theory.
- Title not available (Why is that?)
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Statistical analysis of financial networks
- On the power of unique 2-prover 1-round games
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Parameterized and Exact Computation
- Title not available (Why is that?)
- Path-based depth-first search for strong and biconnected components
- Dividing a Graph into Triconnected Components
- The multi-multiway cut problem
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- Weakly bipartite graphs and the max-cut problem
- Crown structures for vertex cover kernelization
- Vertex cover: Further observations and further improvements
- Facets of the balanced (acyclic) induced subgraph polytope
- Signed graphs for portfolio analysis in risk management
- Short rational generating functions for lattice point problems
- Edge-Deletion Problems
- Experimental and Efficient Algorithms
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- A Local-Search 2-Approximation for 2-Correlation-Clustering
- Algorithms and experiments for parameterized approaches to hard graph problems
- Computing Vertex Connectivity: New Bounds from Old Techniques
- Practical Partitioning-Based Methods for the Steiner Problem
- Fixed-Parameter Algorithms for Cluster Vertex Deletion
- Social balance on networks: the dynamics of friendship and enmity
Cited In (9)
- Optimal Edge Deletions for Signed Graph Balancing
- A modeling and computational study of the frustration index in signed networks
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Linear kernels and linear-time algorithms for finding large cuts
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- 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
- Stabilizing social structure via modifying local patterns
- Evaluating balancing on social networks through the efficient solution of correlation clustering problems
Uses Software
This page was built for publication: Separator-based data reduction for signed graph balancing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q613659)
