Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions

DOI10.1016/j.jda.2011.06.003zbMath1241.05118OpenAlexW2088757584MaRDI QIDQ414467

Alexei Vernitski, Artem V. Pyatkin

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.06.003

zbMATH Keywords

threshold graphclustering coefficientNP-complete problemscale-free graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• Computing independent sets in graphs with large girth
• Star arboricity
• Threshold graphs and related topics
• Emergence of Scaling in Random Networks
• Graph Theory and Probability
• The Dilworth Number of a Graph
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications

This page was built for publication: Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions