A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
From MaRDI portal
Publication:2034399
DOI10.1016/j.tcs.2021.04.023zbMath1506.68074OpenAlexW3158696645MaRDI QIDQ2034399
Yasuaki Kobayashi, Taiga Sone, Tesshu Hanaka
Publication date: 22 June 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.04.023
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of SIMPLE MAX-CUT on comparability graphs
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Some simplified NP-complete graph problems
- Maximum cut on line and total graphs
- Treewidth. Computations and approximations
- Time bounds for selection
- An optimal algorithm for bisection for bounded-treewidth graph
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Minimum bisection is NP-hard on unit disk graphs
- Bisection of bounded treewidth graphs by convolutions
- Clustered Integer 3SUM via Additive Combinatorics
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- Better Approximations for Tree Sparsity in Nearly-Linear Time
- Reducibility among Combinatorial Problems
- Unifying maximum cut and minimum cut of a planar graph
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- On the complexity of \(k\)-SAT
This page was built for publication: A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
