Balanced judicious bipartition is fixed-parameter tractable
DOI10.4230/LIPICS.FSTTCS.2017.40zbMATH Open1491.05148OpenAlexW2792420076MaRDI QIDQ5136332FDOQ5136332
Authors: Daniel Lokshtanov, Saket Saurabh, Roohani Sharma, Meirav Zehavi 
Publication date: 25 November 2020
Full work available at URL: http://dblp.uni-trier.de/db/conf/fsttcs/fsttcs2017.html#LokshtanovSSZ17
Recommendations
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Parameterizing above or below guaranteed values
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterized graph separation problems
- Judicious partitions of hypergraphs
- Maximum cuts and judicious partitions in graphs without short cycles
- Exact bounds for judicious partitions of graphs
- Judicious partitions and related problems
- On judicious bisections of graphs
- Title not available (Why is that?)
- Problems and results on judicious partitions
- Judicious partitions of uniform hypergraphs
- Some Extremal Properties of Bipartite Subgraphs
- Judicious \(k\)-partitions of graphs
- Judicious partitions of 3-uniform hypergraphs
- Balanced judicious bipartitions of graphs
- On judicious bipartitions of graphs
- Judicious partitions of graphs
- An improved parameterized algorithm for the minimum node multiway cut problem
- Judicious partitions of bounded‐degree graphs
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
- Faster parameterized algorithms using linear programming
- Note on maximal bisection above tight lower bound
- Max \(k\)-cut and judicious \(k\)-partitions
- Maximum balanced subgraph problem parameterized above lower bound
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Bisections above Tight Lower Bounds
- Minimum bisection is fixed parameter tractable
- Designing FPT algorithms for cut problems using randomized contractions
- Representative families: a unified tradeoff-based approach
- Judicious partitions of directed graphs
- Linear kernels and linear-time algorithms for finding large cuts
- Parameterized algorithms for load coloring problem
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Parameterized and approximation algorithms for the load coloring problem
- Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
- \((k,n-k)\)-max-cut: an \({\mathcal O}^*(2^p)\)-time algorithm and a polynomial kernel
Cited In (6)
- Balanced Judicious Bipartition is Fixed-Parameter Tractable
- An improved kernel for max-bisection above tight lower bound
- Parameterized complexity of multi-node hubs
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- Parameterized complexity of multi-node hubs
This page was built for publication: Balanced judicious bipartition is fixed-parameter tractable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136332)
