Greedy algorithms for minimisation problems in random regular graphs

DOI10.1007/3-540-44676-1_44MaRDI QIDQ4796200zbMATH OpenFDO

Authors Michele Zito

Publication date 2 March 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2161/21610524

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
• Minimum connected dominating sets in finite graphs
• Analysis of greedy algorithms on graphs with bounded degrees
• On the Independent Domination Number of Random Regular Graphs
• Small k-dominating sets of regular graphs

Cited in

(13)

• Connected domination of regular graphs
• An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm
• Analysis of greedy algorithms on graphs with bounded degrees
• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem
• On the power of random greedy algorithms
• An almost-greedy search on random binary vectors and random graphs
• Greedy Local Search and Vertex Cover in Sparse Random Graphs
• scientific article; zbMATH DE number 1857640 (Why is no real title available?)
• A structural approach for independent domination of regular graphs
• Independent dominating sets in graphs of girth five
• scientific article; zbMATH DE number 6469169 (Why is no real title available?)
• Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
• Greedy-type resistance of combinatorial problems

This page was built for publication: Greedy algorithms for minimisation problems in random regular graphs

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