most citedExact Exponential Time Algorithms for Max Internal Spanning Tree

7 citations · 10 across the 3 of their papers we have counts for

collaborators
Showing cs.DSShow all

3 papers · 1 filter

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^…

cs.DS2008★ 2 cited

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…