𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximations to clustering and subgraph problems on trees

✍ Scribed by Rainer Schrader

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
537 KB
Volume
6
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On multiple steiner subgraph problems
On multiple steiner subgraph problems
✍ M. B. Richey; R. Gary Parker πŸ“‚ Article πŸ“… 1986 πŸ› John Wiley and Sons 🌐 English βš– 752 KB
On the approximability of the Steiner tr
On the approximability of the Steiner tree problem
✍ Martin Thimm πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisΓΏability of linear equation modulo 2. The improvement on the

Fast partitioning l-apex graphs with app
Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems
✍ Dimitrios M. Thilikos; Hans L. Bodlaender πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 542 KB

A graph is Z-apex if it can be made planar by removing at most 1 vertices. In this paper we show that the vertex set of any graph not containing an l-apex graph as a minor can be partitioned in linear time into 2' sets inducing graphs with small treewidth. As a consequence, several maximum induced-s