5 citations · 11 across the 5 of their papers we have counts for
5 papers · 1 filter
Connecting Terminals and 2-Disjoint Connected Subgraphs
Jan Arne Telle, Yngve Villanger
Given a graph and a set of terminal vertices we say that a superset of is -connecting if induces a connected graph, and is minimal if no strict sub…
Generating All Minimal Edge Dominating Sets with Incremental-Polynomial Delay
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch +1
For an arbitrary undirected simple graph G with m edges, we give an algorithm with running time O(m^4 |L|^2) to generate the set L of all minimal edge dominating sets of G. For bip…
Subexponential Parameterized Algorithm for Minimum Fill-in
Fedor V. Fomin, Yngve Villanger
The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable in…
Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves
Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov +3
The {\sc -Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) with at least leaves in a given digraph. The problem has recently re…
Treewidth computation and extremal combinatorics
Fedor V. Fomin, Yngve Villanger
For a given graph G and integers b,f >= 0, let S be a subset of vertices of G of size b+1 such that the subgraph of G induced by S is connected and S can be separated from other ve…