Finding minimum weight connected dominating set in stochastic graph based on learning automata

DOI10.1016/j.ins.2012.02.057zbMath1248.05131OpenAlexW2134648356MaRDI QIDQ712488

D. Kharzeev

Publication date: 17 October 2012

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2012.02.057

zbMATH Keywords

learning automatadominating setminimum connected dominating setstochastic graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Formal languages and automata (68Q45) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Link prediction based on temporal similarity metrics using continuous action set learning automata ⋮ Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata ⋮ Dominating problems in swapped networks ⋮ An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks ⋮ An optimal time algorithm for minimum linear arrangement of chord graphs ⋮ A NEW APPROACH TO THE VERTEX COLORING PROBLEM ⋮ A novel technique for stochastic root-finding: enhancing the search with adaptive \(d\)-ary search

Cites Work

• Unnamed Item
• Unnamed Item
• A linear kernel for a planar connected dominating set
• On the \(k\)-tuple domination of generalized de Brujin and Kautz digraphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks
• Minimum spanning trees in networks with varying edge weights
• Efficient algorithms for the minimum connected domination on trapezoid graphs
• A self-stabilizing algorithm for constructing weakly connected minimal dominating sets
• Dominating sets in directed graphs
• Construction of strongly connected dominating sets in asymmetric multihop wireless networks
• Unit disk graphs
• Approximation algorithms for connected dominating sets
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Bounds on the Convergence Probabilities of Learning Automata
• Simple heuristics for unit disk graphs
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS

This page was built for publication: Finding minimum weight connected dominating set in stochastic graph based on learning automata