On the probable behaviour of some algorithms for finding the stability number of a graph

DOI10.1017/S0305004100060205zbMath0525.05052MaRDI QIDQ3039396

Boris G. Pittel

Publication date: 1982

Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

zbMATH Keywords

stability numberstable setsbinary search treeconstant average degreeconstant edge-density

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)

Related Items (12)

Energy landscape for large average submatrix detection problems in Gaussian random matrices ⋮ On tree census and the giant component in sparse random graphs ⋮ On comparing algorithms for the maximum clique problem ⋮ Giant descendant trees, matchings, and independent sets in age-biased attachment graphs ⋮ Large deviations of the greedy independent set algorithm on sparse random graphs ⋮ Large Deviation Principle for the Greedy Exploration Algorithm over Erd\"os-R\'enyi Graphs ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Rainbow Arborescence in Random Digraphs ⋮ Hamiltonicity in random directed graphs is born resilient ⋮ A Random Graph With a Subcritical Number of Edges ⋮ The maximum clique problem

Cites Work

• Finding a Maximum Independent Set
• Determining the Stability Number of a Graph
• Determining the Chromatic Number of a Graph

This page was built for publication: On the probable behaviour of some algorithms for finding the stability number of a graph