DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2022.40

Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach

Authors: Sharareh Alipour and Mohammadhadi Salari

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

In this paper, we study the minimum dominating set (MDS) problem and the minimum total dominating set (MTDS) problem. We propose a new idea to compute approximate MDS and MTDS. This new approach can be implemented in a distributed model or parallel model. We also show how to use this new approach in other related problems such as set cover problem and k-distance dominating set problem.

Cite as

Sharareh Alipour and Mohammadhadi Salari. Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 40:1-40:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alipour_et_al:LIPIcs.DISC.2022.40,
  author =	{Alipour, Sharareh and Salari, Mohammadhadi},
  title =	{{Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{40:1--40:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.40},
  URN =		{urn:nbn:de:0030-drops-172315},
  doi =		{10.4230/LIPIcs.DISC.2022.40},
  annote =	{Keywords: Minimum dominating set problem, set cover problem, k-distance dominating set problem, distributed algorithms}
}

Search Results

Documents authored by Alipour, Sharareh

Brief Announcement: Distributed Algorithms for Minimum Dominating Set Problem and Beyond, a New Approach

Abstract

Cite as

Thanks for your feedback!

Could not send message