Bisection of bounded treewidth graphs by convolutions

DOI10.1016/J.JCSS.2021.02.002MaRDI QIDQ2662673zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Daniel Lokshtanov, Amer E. Mouawad

Publication date 14 April 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11163/

zbMATH Keywords

bisectionconvolutionfine-grained complexitytreewidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• 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
• Minimum bisection is fixed parameter tractable
• Minimum bisection is fixed-parameter tractable

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A parallel algorithm for bisection width in trees
• A polylogarithmic approximation of the minimum bisection
• Approximating the minimum bisection size (extended abstract)
• Better approximations for tree sparsity in nearly-linear time
• Clustered Integer 3SUM via Additive Combinatorics
• scientific article; zbMATH DE number 1688377 (Why is no real title available?)
• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimum bisection is fixed parameter tractable
• On problems equivalent to \((\min,+)\)-convolution
• On some fine-grained questions in algorithms and complexity
• On the parameterized complexity of computing graph bisections
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Partitioning Planar Graphs
• Subcubic equivalences between path, matrix, and triangle problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
• Treewidth. Computations and approximations

Cited in

(5)

• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
• Bisection of bounded treewidth graphs by convolutions
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Solving cut-problems in quadratic time for graphs with bounded treewidth

This page was built for publication: Bisection of bounded treewidth graphs by convolutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2662673)