Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions
From MaRDI portal
Publication:414467
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
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 t2/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