Expert Systems with Applications
Expert Systems with Applications
5 years ago

Improved solution strategies for dominating trees

Intelligent systems in Wireless Sensor Networks (WSN) allow to eliminate duplicated sensed data and to efficiently route them to a central processing unit. Thus, augmenting WSN lifetime while keeping sensors connectivity and routing the sensed information through an optimized network structure. This work discusses a set of improved exact solution strategies that were effective to the design of a minimum energy consumption structure for the sensors data communication. We present an extended version of a primal-dual model for the minimum cost dominating tree (DT) problem, as well as valid inequalities to improve its linear relaxation. We discuss structural properties of dominating sets and trees used to conceive efficient cutting plane strategies. We adapt accordingly reduction techniques from dominating sets to the DT problem. The new solution techniques allow to handle to optimality challenging benchmark and new randomly generated DT instances with up to 100 nodes, which was not possible to achieve with state-of-the-art models for the problem.

Publisher URL: www.sciencedirect.com/science

DOI: S095741741830037X

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.