Separator-based data reduction for signed graph balancing
From MaRDI portal
Publication:613659
DOI10.1007/s10878-009-9212-2zbMath1206.90201OpenAlexW2030737920MaRDI QIDQ613659
Rolf Niedermeier, Nadja Betzler, Falk Hüffner
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
exact algorithmfinancial networkpreprocessingalgorithm engineeringparameterized algorithmicsgene-regulatory network
Related Items
Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ Stabilizing social structure via modifying local patterns ⋮ A modeling and computational study of the frustration index in signed networks ⋮ Evaluating balancing on social networks through the efficient solution of correlation clustering problems ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Unnamed Item ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Path-based depth-first search for strong and biconnected components
- Finding odd cycle transversals.
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Social balance on networks: the dynamics of friendship and enmity
- The multi-multiway cut problem
- Statistical analysis of financial networks
- Facets of the balanced (acyclic) induced subgraph polytope
- Weakly bipartite graphs and the max-cut problem
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Optimization, approximation, and complexity classes
- A mathematical bibliography of signed and gain graphs and allied areas
- Crown structures for vertex cover kernelization
- Parametrized complexity theory.
- Mining market data: a network approach
- On the notion of balance of a signed graph
- Vertex Cover: Further Observations and Further Improvements
- Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
- A Local-Search 2-Approximation for 2-Correlation-Clustering
- On the power of unique 2-prover 1-round games
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Edge-Deletion Problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Short rational generating functions for lattice point problems
- Signed graphs for portfolio analysis in risk management
- Dividing a Graph into Triconnected Components
- Computing Vertex Connectivity: New Bounds from Old Techniques
- Practical Partitioning-Based Methods for the Steiner Problem
- Parameterized and Exact Computation
- Fixed-Parameter Algorithms for Cluster Vertex Deletion
- Experimental and Efficient Algorithms
This page was built for publication: Separator-based data reduction for signed graph balancing
