7 citations · 8 across the 3 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2009
A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem
Daniel Raible, Henning Fernau
Given a directed graph , the Directed Maximum Leaf Spanning Tree problem asks to compute a directed spanning tree (i.e., an out-branching) with as many leaves as possible.…
cs.DS2008★ 7 cited
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…
cs.DS2008★ 1 cited
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^…