Greed is good for deterministic scale-free networks

DOI10.1007/s00453-020-00729-zzbMath1477.68212MaRDI QIDQ2205637

Tobias Friedrich, Ankit Chauhan, Ralf Rothenberger

Publication date: 21 October 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00729-z

zbMATH Keywords

approximation; random graphs; APX-hardness; power-law; deterministic properties

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C80: Random graphs (graph-theoretic aspects)

68R10: Graph theory (including graph drawing) in computer science

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

68W25: Approximation algorithms

Uses Software

• SNAP