[go: up one dir, main page]
Skip to main content
We gratefully acknowledge support from the Simons Foundation, member institutions, and all contributors. Donate
arXiv logo
Cornell University Logo

Mathematics > Combinatorics

arXiv:2203.00799 (math)
[Submitted on 2 Mar 2022 (v1), last revised 22 Jan 2024 (this version, v2)]

Title:Weighted domination models and randomized heuristics

Authors:Lukas Dijkstra, Andrei Gagarin, Vadim Zverovich
View PDF
Abstract:We consider the minimum weight and smallest weight minimum-size dominating set problems in vertex-weighted graphs and networks. The latter problem is a two-objective optimization problem, which is different from the classic minimum weight dominating set problem that requires finding a dominating set of the smallest weight in a graph without trying to optimize its cardinality. In other words, the objective of minimizing the size of the dominating set in the two-objective problem can be considered as a constraint, i.e. a particular case of finding Pareto-optimal solutions. First, we show how to reduce the two-objective optimization problem to the minimum weight dominating set problem by using Integer Linear Programming formulations. Then, under different assumptions, the probabilistic method is applied to obtain upper bounds on the minimum weight dominating sets in graphs. The corresponding randomized algorithms for finding small-weight dominating sets in graphs are described as well. Computational experiments are used to illustrate the results for two different types of random graphs.
Comments: 35 pages, 4 figures, 8 tables; enhanced version from October 2023; presented at the 10th International Network Optimization Conference, INOC 2022, Aachen, Germany, June 7-10, 2022, extended abstract at this https URL
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
MSC classes: 05C69, 68W20, 05C85, 68R10, 90B15, 90C10, 90C35
Cite as: arXiv:2203.00799 [math.CO]
  (or arXiv:2203.00799v2 [math.CO] for this version)
  https://doi.org/10.48550/arXiv.2203.00799

Submission history

From: Andrei Gagarin [view email]
[v1] Wed, 2 Mar 2022 00:08:04 UTC (48 KB)
[v2] Mon, 22 Jan 2024 16:19:10 UTC (55 KB)
Full-text links:

Access Paper:

license icon view license
Current browse context:
math.CO
< prev   |   next >
new | recent | 2022-03
Change to browse by:
cs
cs.DM
math

References & Citations

export BibTeX citation

Bookmark

BibSonomy logo Reddit logo

Bibliographic and Citation Tools

Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)

Code, Data and Media Associated with this Article

alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)

Demos

Replicate (What is Replicate?)
Hugging Face Spaces (What is Spaces?)
TXYZ.AI (What is TXYZ.AI?)

Recommenders and Search Tools

Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)