Minimum Bisection Is Fixed-Parameter Tractable
From MaRDI portal
Publication:4634024
DOI10.1137/140988553zbMath1421.68069OpenAlexW2937927637MaRDI QIDQ4634024
Marcin Pilipczuk, Michał Pilipczuk, Marek Cygan, Saket Saurabh, Daniel Lokshtanov
Publication date: 7 May 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/66072/1/WRAP_1371795-cs-270115-bisection.pdf
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (4)
Finding connected secluded subgraphs ⋮ First-order Logic with Connectivity Operators ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connectivity and tree structure in finite graphs
- On the parameterized complexity of computing balanced partitions in graphs
- Parameterized graph separation problems
- A Menger-like property of tree-width: The finite case
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Graph minors. XIII: The disjoint paths problem
- An improved parameterized algorithm for the minimum node multiway cut problem
- A Polylogarithmic Approximation of the Minimum Bisection
- On the Parameterized Complexity of Computing Graph Bisections
- Finding small balanced separators
- Finding small separators in linear time via treewidth reduction
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Approximating the minimum bisection size (extended abstract)
- Partitioning Planar Graphs
- Color-coding
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Minimum bisection is fixed parameter tractable
- Finding topological subgraphs 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
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
This page was built for publication: Minimum Bisection Is Fixed-Parameter Tractable
