Solving cut-problems in quadratic time for graphs with bounded treewidth

DOI10.1007/978-3-031-23101-8_3arXiv2101.00694OpenAlexW4313429567MaRDI QIDQ6114456

Hauke Brinkop, Klaus Jansen

Publication date: 14 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2101.00694

Mathematics Subject Classification ID

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

Cites Work

• The complexity of finding uniform sparsest cuts in various graph classes
• On the complexity of finding balanced oneway cuts
• Treewidth. Computations and approximations
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Bisection of bounded treewidth graphs by convolutions
• The Complexity of Satisfiability of Small Depth Circuits
• Approximation algorithms for NP-complete problems on planar graphs
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• On Problems Equivalent to (min,+)-Convolution
• Reducibility among Combinatorial Problems
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• On the complexity of \(k\)-SAT

This page was built for publication: Solving cut-problems in quadratic time for graphs with bounded treewidth