๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An improved fixed-parameter algorithm for vertex cover

โœ Scribed by R. Balasubramanian; Michael R. Fellows; Venkatesh Raman

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
546 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

The VERTEX COVER problem asks, for input consisting of a graph G on n vertices, and a positive integer k, whether there is a set of k vertices such that every edge of G is incident with at least one of these vertices. We give an algorithm for this problem that runs in time O(kn + (1.324718)'k'). In particular, this gives an 0( ( 1.324718)"n2) algorithm to find the minimum vertex cover in the graph. @

๐Ÿ“œ SIMILAR VOLUMES

An Efficient Exact Algorithm for Constra
An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
โœ Henning Fernau; Rolf Niedermeier ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 382 KB

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k 1 k 2 , is there a vertex cover taking at most k 1 vertices from one and at most k 2 vertices from the other vertex set of G? CBVC is NP-complete. It fo

An algorithm for vertex detection
An algorithm for vertex detection
โœ S. Anand; S. Raman; R.A. Wysk ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 900 KB
A fixed-parameter algorithm for minimum
A fixed-parameter algorithm for minimum quartet inconsistency
โœ Jens Gramm; Rolf Niedermeier ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 285 KB

Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the Minimum Quartet Inconsistency (MQI) problem is the question whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in only k quartet