Minimum bisection is fixed-parameter tractable
From MaRDI portal
Recommendations
- Minimum bisection is fixed parameter tractable
- On the parameterized complexity of computing graph bisections
- Bisections above Tight Lower Bounds
- On minimum bisection and related partition problems in graphs with bounded tree width
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
Cites work
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A Menger-like property of tree-width: The finite case
- A polylogarithmic approximation of the minimum bisection
- An improved parameterized algorithm for the minimum node multiway cut problem
- Approximating the minimum bisection size (extended abstract)
- Color-coding
- Connectivity and tree structure in finite graphs
- Designing FPT algorithms for cut problems using randomized contractions
- Finding small balanced separators
- Finding small separators in linear time via treewidth reduction
- Finding topological subgraphs is fixed-parameter tractable
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Graph minors. XIII: The disjoint paths problem
- scientific article; zbMATH DE number 5485537 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1870231 (Why is no real title available?)
- Minimum bisection is fixed parameter tractable
- On the parameterized complexity of computing balanced partitions in graphs
- On the parameterized complexity of computing graph bisections
- Parameterized graph separation problems
- Partitioning Planar Graphs
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
- The minimum k-way cut of bounded size is fixed-parameter tractable
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
Cited in
(27)- A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- Finding connected secluded subgraphs
- Minimum bisection is NP-hard on unit disk graphs
- Bisection of bounded treewidth graphs by convolutions
- A polylogarithmic approximation of the minimum bisection
- On the parameterized complexity of computing graph bisections
- Approximating the minimum bisection size (extended abstract)
- On minimum bisection and related partition problems in graphs with bounded tree width
- On minimum bisection and related cut problems in trees and tree-like graphs
- Randomized Contractions Meet Lean Decompositions
- A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
- Minimum bisection is fixed parameter tractable
- First-order Logic with Connectivity Operators
- A survey of parameterized algorithms and the complexity of edge modification
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Flow-augmentation. I: Directed graphs
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Model checking disjoint-paths logic on topological-minor-free graph classes
- Flow-augmentation. II: Undirected graphs
- Compound logics for modification problems
- Exploiting dense structures in parameterized complexity
- Breaking a graph into connected components with small dominating sets
- Equitable connected partition and structural parameters revisited: N-fold beats Lenstra
- Advances in algorithmic meta theorems (invited paper)
- Elimination distance to dominated clusters
- All-subsets important separators with applications to sample sets, balanced separators and vertex sparsifiers in directed graphs
This page was built for publication: Minimum bisection is fixed-parameter tractable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634024)
