5 papers · 1 filter
Optimized 2-Approximation of Treewidth
Mahdi Belbasi, Martin Fürer, Medha Kumar
This paper presents a linear FPT algorithm to find a tree decomposition with a 2-approximation of the treewidth with a significantly smaller exponential dependence on the treewidth…
Finding All Leftmost Separators of Size
Mahdi Belbasi, Martin Fürer
We define a notion called leftmost separator of size at most . A leftmost separator of size is a minimal separator that separates two given sets of vertices and …
An Improvement of Reed's Treewidth Approximation
Mahdi Belbasi, Martin Fürer
We present a new approximation algorithm for the treewidth problem which finds an upper bound on the treewidth and constructs a corresponding tree decomposition as well. Our algori…
A Space-efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraziation
Mahdi Belbasi, Martin Fürer
An NP-hard graph problem may be intractable for general graphs but it could be efficiently solvable using dynamic programming for graphs with bounded width (or depth or some other…
Saving Space by Dynamic Algebraization Based on Tree Decomposition: Minimum Dominating Set
Mahdi Belbasi, Martin Fürer
An algorithm is presented that solves the Minimum Dominating Set problem exactly using polynomial space based on dynamic programming for a tree decomposition. A direct application…