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

DOI10.1051/ro/2014040zbMath1314.05145OpenAlexW2017267326MaRDI QIDQ5247696

Djelloul Memeri, Jean Mailfert, Fatiha Bendali

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 setwireless sensor networksimplicit enumerationmaximal independent setminimum weakly connected independent set

Mathematics Subject Classification ID

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

Related Items (2)

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

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the minimum maximal independence number
• On approximating the minimum independent dominating set
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Clustering and domination in perfect graphs
• On generating all maximal independent sets
• Independent domination in chordal graphs
• Unit disk graphs
• On weakly connected domination in graphs
• Approximation algorithms for connected dominating sets
• Fast algorithms for min independent dominating set
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Domination in permutation graphs
• TSPLIB—A Traveling Salesman Problem Library
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• Integer Programming by Implicit Enumeration and Balas’ Method
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• On cliques in graphs

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