𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximations for the maximum acyclic subgraph problem

✍ Scribed by Refael Hassin; Shlomi Rubinstein

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
722 KB
Volume
51
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ 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

Local approximations for maximum partial
Local approximations for maximum partial subgraph problem
✍ JΓ©rΓ΄me Monnot; Vangelis Th. Paschos; Sophie Toulouse πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 232 KB

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 p

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