Inapproximability of dominating set on power law graphs

DOI10.1016/j.tcs.2014.10.021zbMath1305.05174arXiv1212.3517MaRDI QIDQ476891

Marek Karpinski, Mikael Gast, Mathias Hauptmann

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimization; dominating set; approximation algorithms; inapproximability; power law graphs

Mathematics Subject Classification ID

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W25: Approximation algorithms

Related Items

EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET, COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB, Minimum vertex cover in generalized random graphs with power law degree distribution, Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph, An order-based algorithm for minimum dominating set with application in graph mining, Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, Greed is good for deterministic scale-free networks, Combinatorial properties of Farey graphs, Near-Optimal Dominating Sets via Random Sampling

Cites Work

• Unnamed Item
• Unnamed Item
• Approximability of the vertex cover problem in power-law graphs
• New techniques for approximating optimal substructure problems in power-law graphs
• Renormalization group analysis of the small-world network model
• Popularity based random graph models leading to a scale-free degree sequence
• On the hardness of optimization in power-law graphs
• A Random Graph Model for Power Law Graphs
• Emergence of Scaling in Random Networks
• A threshold of ln n for approximating set cover
• A random graph model for massive graphs