Near-optimal dominating sets in dense random graphs in polynomial expected time

DOI10.1007/3-540-57899-4_36zbMath1530.05173OpenAlexW1494324938MaRDI QIDQ6184387

Sotiris E. Nikoletseas, Paul G. Spirakis

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-57899-4_36

zbMATH Keywords

second moment method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Average case completeness
• Hamiltonian circuits in random graphs
• The solution of some random NP-hard problems in polynomial expected time
• Average Case Complete Problems
• On colouring random graphs

This page was built for publication: Near-optimal dominating sets in dense random graphs in polynomial expected time