𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating minimum feedback vertex sets in hypergraphs

✍ Scribed by Toshihiro Fujito

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
102 KB
Volume
246
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Minimum feedback vertex set and acyclic
Minimum feedback vertex set and acyclic coloring
✍ Guillaume Fertin; Emmanuel Godard; AndrΓ© Raspaud πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 132 KB

In the feedback vertex set problem, the aim is to minimize, in a connected graph G = (V , E), the cardinality of the set V (G) βŠ† V , whose removal induces an acyclic subgraph. In this paper, we show an interesting relationship between the minimum feedback vertex set problem and the acyclic coloring

Minimum feedback vertex sets in shuffle-
Minimum feedback vertex sets in shuffle-based interconnection networks
✍ Rastislav KrΓ‘lovič; Peter RuΕΎička πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 120 KB

Given a graph G, the problem is to construct a smallest subset S of vertices whose deletion results in an acyclic subgraph. The set S is called a minimum feedback vertex set for G. Tight upper and lower bounds on the cardinality of minimum feedback vertex sets have been previously obtained for some

Approximating Coloring and Maximum Indep
Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
✍ Michael Krivelevich; Ram Nathaniel; Benny Sudakov πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 120 KB

We discuss approximation algorithms for the coloring problem and the maximum independent set problem in 3-uniform hypergraphs. An algorithm for coloring ˜1r5 Ε½ . ## 3-uniform 2-colorable hypergraphs in O n colors is presented, improving previously known results. Also, for every fixed β₯ ) 1r2, we