19 citations · 75 across the 31 of their papers we have counts for
4 papers · 1 filter
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…
Exact Exponential Time Algorithms for Max Internal Spanning Tree
Henning Fernau, Serge Gaspers, Daniel Raible
We consider the NP-hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our…
A New Upper Bound for Max-2-Sat: A Graph-Theoretic Approach
Daniel Raible, Henning Fernau
In {\sc MaxSat}, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of $O^…
A Parameterized Perspective on -Packings
Jianer Chen, Henning Fernau, Dan Ning +2
}We study (vertex-disjoint) -packings in graphs under a parameterized perspective. Starting from a maximal -packing $\p$ of size we use extremal arguments for determi…