Maximum balanced subgraph problem parameterized above lower bound
From MaRDI portal
Publication:391973
DOI10.1016/j.tcs.2013.10.026zbMath1396.68054OpenAlexW2186158012MaRDI QIDQ391973
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items (6)
Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ The balanced connected subgraph problem ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized complexity of multi-node hubs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Parameterizing above or below guaranteed values
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- A mathematical bibliography of signed and gain graphs and allied areas
- Extracting pure network submatrices in linear programs using signed graphs.
- Note on maximal bisection above tight lower bound
- Parametrized complexity theory.
- On the notion of balance of a signed graph
- Max-Cut Parameterized above the Edwards-Erdős Bound
- Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
- Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Optimal Edge Deletions for Signed Graph Balancing
This page was built for publication: Maximum balanced subgraph problem parameterized above lower bound
