Balanced Judicious Bipartition is Fixed-Parameter Tractable
DOI10.1137/17M1155612zbMath1425.05129arXiv1710.05491OpenAlexW2979456162WikidataQ127126725 ScholiaQ127126725MaRDI QIDQ5238741
Daniel Lokshtanov, Roohani Sharma, Saket Saurabh, Meirav Zehavi
Publication date: 28 October 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.05491
tree decompositionjudicious partitionfixed-parameter tractableminimum bisectionrandomized contractions
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum balanced subgraph problem parameterized above lower bound
- On judicious bisections of graphs
- Judicious partitions of uniform hypergraphs
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Parameterized graph separation problems
- Representative families: a unified tradeoff-based approach
- Max \(k\)-cut and judicious \(k\)-partitions
- Judicious \(k\)-partitions of graphs
- Parameterizing above or below guaranteed values
- Judicious partitions of graphs
- Judicious partitions of hypergraphs
- Maximum cuts and judicious partitions in graphs without short cycles
- Note on maximal bisection above tight lower bound
- Judicious partitions of 3-uniform hypergraphs
- Exact bounds for judicious partitions of graphs
- Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
- An improved parameterized algorithm for the minimum node multiway cut problem
- Parameterized and approximation algorithms for the load coloring problem
- Parameterized algorithms for load coloring problem
- $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Judicious partitions of directed graphs
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Judicious partitions of bounded‐degree graphs
- Linear Kernels and Linear-Time Algorithms for Finding Large Cuts
- Problems and results on judicious partitions
- Faster Parameterized Algorithms Using Linear Programming
- Balanced judicious bipartitions of graphs
- Bisections above Tight Lower Bounds
- Minimum bisection is fixed parameter tractable
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Some Extremal Properties of Bipartite Subgraphs
- On judicious bipartitions of graphs
This page was built for publication: Balanced Judicious Bipartition is Fixed-Parameter Tractable
