On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm

DOI10.1051/RO/2014040MaRDI QIDQ5247696zbMATH OpenOpenAlexFDO

Authors Djelloul Memeri, F. Bendali, J. Mailfert

Publication date 27 April 2015

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/41a5d03a0351fcc5fdd642e9ca7e2dd77c6e52eb

zbMATH Keywords

approximationdominating setimplicit enumerationmaximal independent setminimum weakly connected independent setwireless sensor networks

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Constructing weakly connected dominating set for secure clustering in distributed sensor network
• The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• Finding a maximal weighted independent set in wireless networks
• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

Cites work

• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Approximating the minimum maximal independence number
• Approximation algorithms for connected dominating sets
• Clustering and domination in perfect graphs
• Domination in permutation graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• Fast algorithms for min independent dominating set
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 2209525 (Why is no real title available?)
• Independent domination in chordal graphs
• Integer Programming by Implicit Enumeration and Balas’ Method
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• On approximating the minimum independent dominating set
• On cliques in graphs
• On generating all maximal independent sets
• On weakly connected domination in graphs
• Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic
• TSPLIB—A Traveling Salesman Problem Library
• Unit disk graphs

Cited in

(5)

• The weakly connected independent set polytope in corona and join of graphs
• The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
• Matrix formulation of EISs of graphs and its application to WSN covering problems
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• Approximating minimum independent dominating sets in wireless networks

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm

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