7 citations · 18 across the 15 of their papers we have counts for
18 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 …
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…
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…
On the Combinatorial Power of the Weisfeiler-Lehman Algorithm
Martin Fürer
The classical Weisfeiler-Lehman method WL[2] uses edge colors to produce a powerful graph invariant. It is at least as powerful in its ability to distinguish non-isomorphic graphs…
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…
Multi-Clique-Width
Martin Fürer
Multi-clique-width is obtained by a simple modification in the definition of clique-width. It has the advantage of providing a natural extension of tree-width. Unlike clique-width,…
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…
Counting cliques and clique covers in random graphs
Kashyap Dixit, Martin Fürer
We study the problem of counting the number of {\em isomorphic} copies of a given {\em template} graph, say , in the input {\em base} graph, say . In general, it is believed…
Space Saving by Dynamic Algebraization
Martin Furer, Huiwen Yu
Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study th…
How Fast Can We Multiply Large Integers on an Actual Computer?
Martin Fürer
We provide two complexity measures that can be used to measure the running time of algorithms to compute multiplications of long integers. The random access machine with unit or lo…
A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
Martin Fürer
We investigate a new width parameter, the fusion-width of a graph. It is a natural generalization of the tree-width, yet strong enough that not only graphs of bounded tree-width, b…
Approximate the k-Set Packing Problem by Local Improvements
Martin Furer, Huiwen Yu
We study algorithms based on local improvements for the -Set Packing problem. The well-known local improvement algorithm by Hurkens and Schrijver has been improved by Sviridenko…
Packing-Based Approximation Algorithm for the k-Set Cover Problem
Martin Furer, Huiwen Yu
We present a packing-based approximation algorithm for the -Set Cover problem. We introduce a new local search-based -set packing heuristic, and call it Restricted -Set Pa…
An Exponential Time 2-Approximation Algorithm for Bandwidth
Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan
The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by a…
Approximately Counting Embeddings into Random Graphs
Martin Furer, Shiva Prasad Kasiviswanathan
Let H be a graph, and let C_H(G) be the number of (subgraph isomorphic) copies of H contained in a graph G. We investigate the fundamental problem of estimating C_H(G). Previous re…
Spanners for Geometric Intersection Graphs
Martin Furer, Shiva Prasad Kasiviswanathan
Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+ε)-spanner is obtained using efficient partitionin…