𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating edge dominating set in dense graphs

✍ Scribed by Richard Schmied; Claus Viehmann

Book ID
113927565
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
260 KB
Volume
414
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Edge-dominating cycles in graphs
Edge-dominating cycles in graphs
✍ Shinya Fujita; Akira Saito; Tomoki Yamashita πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 181 KB
Approximation hardness of edge dominatin
Approximation hardness of edge dominating set problems
✍ Miroslav ChlebΓ­k; Janka ChlebΓ­kovΓ‘ πŸ“‚ Article πŸ“… 2006 πŸ› Springer US 🌐 English βš– 324 KB

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor

Set domination in graphs
Set domination in graphs
✍ E. Sampathkumar; L. Pushpa Latha πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 355 KB

## Abstract Let __G__ = (__V, E__) be a connected graph. A set __D__ βŠ‚ __V__ is a __set‐dominating set__ (sd‐set) if for every set __T__ βŠ‚ __V__ βˆ’ __D__, there exists a nonempty set __S__ βŠ‚ __D__ such that the subgraph γ€ˆ__S__ βˆͺ __T__〉 induced by __S__ βˆͺ __T__ is connected. The set‐domination number