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

DOI10.1017/S0305004100060205zbMATH Open0525.05052MaRDI QIDQ3039396FDOQ3039396

Authors: Boris 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)

Cites Work

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

Cited In (13)

• Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
• Rainbow arborescence in random digraphs
• The maximum clique problem
• Cryptography from planted graphs: security with logarithmic-size messages
• On tree census and the giant component in sparse random graphs
• A Random Graph With a Subcritical Number of Edges
• Graph theory (algorithmic, algebraic, and metric problems)
• On comparing algorithms for the maximum clique problem
• Large deviations of the greedy independent set algorithm on sparse random graphs
• Hamiltonicity in random directed graphs is born resilient
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Energy landscape for large average submatrix detection problems in Gaussian random matrices
• Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3039396)