A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph

PDF Version Also Available for Download.

Description

Article implements and tests the performances of several approximation algorithms for computing the minimum dominating set of a graph. This article belongs to the Special Issue: Algorithms for Hard Graph Problems.

Physical Description

12 p.

Creation Information

Shahrokhi, Farhad; Li, Jonathan & Potru, Rohan December 14, 2020.

Context

This article is part of the collection entitled: UNT Scholarly Works and was provided by the UNT College of Engineering to the UNT Digital Library, a digital repository hosted by the UNT Libraries. More information about this article can be viewed below.

Who

People and organizations associated with either the creation of this article or its content.

Authors

Provided By

UNT College of Engineering

The UNT College of Engineering strives to educate and train engineers and technologists who have the vision to recognize and solve the problems of society. The college comprises six degree-granting departments of instruction and research.

Contact Us

What

Descriptive information to help identify this article. Follow the links below to find similar items on the Digital Library.

Degree Information

Description

Article implements and tests the performances of several approximation algorithms for computing the minimum dominating set of a graph. This article belongs to the Special Issue: Algorithms for Hard Graph Problems.

Physical Description

12 p.

Notes

Abstract: We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent Linear programming (LP) rounding algorithms and a hybrid algorithm that we design by combining the greedy and LP rounding algorithms. Over the range of test data, all algorithms perform better than anticipated in theory, and have small performance ratios, measured as the size of output divided by the LP objective lower bound. However, each have advantages over the others. For instance, LP rounding algorithm normally outperforms the other algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP rounding took less than 15 s of CPU time to generate a solution with performance ratio 1.011, while the greedy and hybrid algorithms generated solutions of performance ratio 1.12 in similar time. For synthetic graphs, the hybrid algorithm normally outperforms the others, whereas for hypercubes and k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid algorithm is to solve very large problems that are suitable for application of LP rounding (sparse graphs) but LP formulations become formidable in practice and LP solvers crash, as we observed on a real-world graph with 7.7 million+ vertices and a planar graph on 1,000,000 vertices.

Source

  • Algorithms, 13(12), Multidisciplinary Digital Publishing Institute, December 14, 2020, pp. 1-20

Language

Item Type

Identifier

Unique identifying numbers for this article in the Digital Library or other systems.

Publication Information

  • Publication Title: Algorithms
  • Volume: 13
  • Issue: 12
  • Article Identifier: 339
  • Pages: 12
  • Peer Reviewed: Yes

Collections

This article is part of the following collection of related materials.

UNT Scholarly Works

Materials from the UNT community's research, creative, and scholarly activities and UNT's Open Access Repository. Access to some items in this collection may be restricted.

What responsibilities do I have when using this article?

When

Dates and time periods associated with this article.

Creation Date

  • December 14, 2020

Added to The UNT Digital Library

  • May 27, 2022, 5:53 a.m.

Description Last Updated

  • Nov. 14, 2023, 2:27 p.m.

Usage Statistics

When was this article last used?

Yesterday: 0
Past 30 days: 0
Total Uses: 2

Interact With This Article

Here are some suggestions for what to do next.

Start Reading

PDF Version Also Available for Download.

International Image Interoperability Framework

IIF Logo

We support the IIIF Presentation API

Shahrokhi, Farhad; Li, Jonathan & Potru, Rohan. A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph, article, December 14, 2020; (https://digital.library.unt.edu/ark:/67531/metadc1934111/: accessed February 27, 2024), University of North Texas Libraries, UNT Digital Library, https://digital.library.unt.edu; crediting UNT College of Engineering.

Back to Top of Screen