6 papers
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 …
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…
Eigenvalue location in graphs of small clique-width
Martin Fürer, Carlos Hoppen, David P. Jacobs +1
Finding a diagonal matrix congruent to for constants , where is the adjacency matrix of a graph allows us to quickly tell the number of eigenvalues in a given i…
Faster Computation of Path-Width
Martin Fürer
Tree-width and path-width are widely successful concepts. Many NP-hard problems have efficient solutions when restricted to graphs of bounded tree-width. Many efficient algorithms…
Efficient Computation of the Characteristic Polynomial of a Threshold Graph
Martin Fürer
An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chvátal and Hammer, as well as by Henderson a…