The probabilistic minimum dominating set problem
From MaRDI portal
Publication:1686054
DOI10.1016/j.dam.2016.10.016zbMath1376.05107OpenAlexW2559859930MaRDI QIDQ1686054
Cécile Murat, Nicolas Boria, Vangelis Th. Paschos
Publication date: 20 December 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.10.016
Applications of graph theory (05C90) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ The probabilistic and reliable connected power dominating set problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Wireless multicasting under probabilistic node failures: a heuristic approach
- Combinatorial optimization. Second international symposium, ISCO 2012, Athens, Greece, April 19-21, 2012. Revised selected papers
- The complexity of computing the permanent
- Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms
- Probabilistic graph-coloring in bipartite and split graphs
- Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines
- Estimation-based metaheuristics for the probabilistic traveling salesman problem
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- On the probabilistic min spanning tree problem
- Mixed integer formulations for the probabilistic minimum energy broadcast problem in wireless networks
- Aggregation for the probabilistic traveling salesman problem
- On the probabilistic minimum coloring and minimum \(k\)-coloring
- Some Valid Inequalities for the Probabilistic Minimum Power Multicasting Problem
- Estimation-Based Local Search for Stochastic Combinatorial Optimization Using Delta Evaluations: A Case Study on the Probabilistic Traveling Salesman Problem
- Probabilistic models for the Steiner Tree problem
- A threshold of ln n for approximating set cover
- Hardness Results for the Probabilistic Traveling Salesman Problem with Deadlines
- The probabilistic minimum spanning tree problem
- Steiner Forests on Stochastic Metric Graphs
- A Priori Solution of a Traveling Salesman Problem in Which a Random Subset of the Customers Are Visited
- Shortest path problems with node failures
- The probabilistic longest path problem
- Probabilistic a priori routing-location problems
- The Probabilistic Minimum Vertex-covering Problem
- Traveling Salesman Facility Location Problems
- Reducibility among Combinatorial Problems
- A Priori Optimization
- A priori optimization for the probabilistic maximum independent set problem
