Greedy domination on biclique-free graphs

DOI10.1016/j.ipl.2019.01.006zbMath1446.68198arXiv1806.02590OpenAlexW2963620515WikidataQ128593901 ScholiaQ128593901MaRDI QIDQ1730031

Sebastian Siebertz

Publication date: 11 March 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1806.02590

zbMATH Keywords

approximation algorithmsgreedy algorithmsdominating set problemstructural graph theory

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

A polynomial-time approximation to a minimum dominating set in a graph, Distributed Dominating Set Approximations beyond Planar Graphs, Local planar domination revisited, Constant round distributed domination on graph classes with bounded expansion

Cites Work

• Unnamed Item
• Unnamed Item
• Hitting sets when the VC-dimension is small
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Tight approximation bounds for dominating set on graphs of bounded arboricity
• Almost optimal set covers in finite VC-dimension
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Reducibility among Combinatorial Problems
• Analytical approach to parallel repetition