Improved approximations of independent dominating set in bounded degree graphs

DOI10.1007/3-540-62559-3_2zbMATH Open1539.68206MaRDI QIDQ6550528

Could not fetch data.

Publication date: 5 June 2024

zbMATH Keywords

local searchregular graphscubic graphsapproximation algorithmsbounded-degree graphsminimum independent dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Cites Work

• Approximating the minimum maximal independence number
• Optimization, approximation, and complexity classes
• On the hardness of approximating minimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Improved approximations of independent dominating set in bounded degree graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6550528)