Bisection of bounded treewidth graphs by convolutions
From MaRDI portal
Publication:5075784
DOI10.4230/LIPICS.ESA.2019.42MaRDI QIDQ5075784FDOQ5075784
Authors: Eduard Eiben, Daniel Lokshtanov, Amer E. Mouawad 
Publication date: 11 May 2022
Recommendations
- Bisection of bounded treewidth graphs by convolutions
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- On minimum bisection and related partition problems in graphs with bounded tree width
- Solving cut-problems in quadratic time for graphs with bounded treewidth
- On minimum bisection and related cut problems in trees and tree-like graphs
Cites Work
- Title not available (Why is that?)
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Treewidth. Computations and approximations
- Clustered Integer 3SUM via Additive Combinatorics
- Title not available (Why is that?)
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Title not available (Why is that?)
- A polylogarithmic approximation of the minimum bisection
- A \(c^k n\) 5-approximation algorithm for treewidth
- On the parameterized complexity of computing graph bisections
- Partitioning Planar Graphs
- Subcubic equivalences between path, matrix, and triangle problems
- Minimum bisection is fixed parameter tractable
- The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into \(\ell_1\)
- A parallel algorithm for bisection width in trees
- Approximating the minimum bisection size (extended abstract)
- Better approximations for tree sparsity in nearly-linear time
- On problems equivalent to \((\min,+)\)-convolution
- On some fine-grained questions in algorithms and complexity
Cited In (3)
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 Q5075784)
