𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Local approximations for maximum partial subgraph problem

✍ Scribed by Jérôme Monnot; Vangelis Th. Paschos; Sophie Toulouse

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
232 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

We deal with MAX H0-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio ( 0 + 1)=(B + 2 + 0), where B = maxv∈V dG(v), 0 = min v∈V (H 0 ) dH 0 (v) and 0 = (|V (H0)| + 1)= 0. Next, we show that this ratio rises up to 3=(B + 1) when H0 = K3. Finally, we provide hardness results for MAX K3-FREE PARTIAL SUBGRAPH.

📜 SIMILAR VOLUMES

Tight Bounds for the Maximum Acyclic Sub
Tight Bounds for the Maximum Acyclic Subgraph Problem
✍ Bonnie Berger; Peter W Shor 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 209 KB

Given a directed graph G s V, A , the maximum acyclic subgraph problem is to Ž . find a maximum cardinality subset AЈ of the arcs such that GЈ s V, AЈ is acyclic. In this paper, we present polynomial-time and RNC algorithms which, when given Ž any graph G without two-cycles, find an acyclic subgraph

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