A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
type: Item
instance of: scholarly article
title: A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
zbMATH Open document ID: 1506.68074
author: Tesshu Hanaka
author: Yasuaki Kobayashi
author: Taiga Sone
published in: Theoretical Computer Science
publication date: 2021-06-22T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 7361598
zbMATH Keywords: bisection
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: treewidth
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.04.023
OpenAlex ID: W3158696645
cites work: Reducibility among Combinatorial Problems
cites work: Q5659589
cites work: Finding a Maximum Cut of a Planar Graph in Polynomial Time
cites work: Unifying maximum cut and minimum cut of a planar graph
cites work: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
cites work: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
cites work: Some simplified NP-complete graph problems
cites work: Minimum bisection is NP-hard on unit disk graphs
cites work: Bisection of bounded treewidth graphs by convolutions
cites work: On the complexity of \(k\)-SAT
cites work: An optimal algorithm for bisection for bounded-treewidth graph
cites work: Parallel Algorithms with Optimal Speedup for Bounded Treewidth
cites work: Treewidth. Computations and approximations
cites work: Better Approximations for Tree Sparsity in Nearly-Linear Time
cites work: Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
cites work: Time bounds for selection
cites work: Q4500843
cites work: The complexity of SIMPLE MAX-CUT on comparability graphs
cites work: Maximum cut on line and total graphs
cites work: An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
cites work: A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
cites work: Clustered Integer 3SUM via Additive Combinatorics
DOI: 10.1016/J.TCS.2021.04.023
description: scientific article; zbMATH DE number 7361598