𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Criterions for locally dense subgraphs

✍ Scribed by Gergely Tibély

Book ID
113849277
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
700 KB
Volume
391
Category
Article
ISSN
0378-4371

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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