Metraipolis › archive › dc_fe1e44f3fbac

Computing Forest Degree Realizations with Minimum Cardinality Domination — arXiv:2611.06482

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.06482
License (as archived)
CC0-1.0
Archived
2026-11-05T18:31:40.360Z
SHA-256 of the archived text
88201b24a1e6fc8479ab32edaed5c5d1e675ba80603bf41d33038e912af789c6
Stable URL of this page
https://metraipolis.com/documento/dc_fe1e44f3fbac

How to cite

Computing Forest Degree Realizations with Minimum Cardinality Domination — arXiv:2611.06482 — arXiv (en), https://arxiv.org/abs/2611.06482 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fe1e44f3fbac (Metraipolis archive dc_fe1e44f3fbac, sha256 88201b24a1e6fc8479ab32edaed5c5d1e675ba80603bf41d33038e912af789c6)
BibTeX
@misc{dcfe1e44f3fbac,
  title = {Computing Forest Degree Realizations with Minimum Cardinality Domination — arXiv:2611.06482},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06482},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fe1e44f3fbac; sha256 88201b24a1e6fc8479ab32edaed5c5d1e675ba80603bf41d33038e912af789c6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06482. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the Degree Realization problem with respect to a family $\mathcal{P}$ of graphs the input is a non-increasing sequence $d = (d_1,\ldots,d_n)$ of positive integers, and the goal is to decide whether there exists a simple undirected graph $G \in \mathcal{P}$, whose degrees correspond to $d$, i.e., such that $deg(G) = d$. In this paper we consider the version of Degree Realization in which the realization is required to be a forest (i.e., $\mathcal{P}$ is the family of forests). We consider \emph{optimized} Degree Realization in which the goal is to obtain a realization that minimizes an objective function $f$. That is, the goal is to find a realization $G$ that minimizes $f(G)$ among the realizations of the given input sequence. More specifically, we focus on the following functions: the size of an optimal \emph{vertex cover} and the size of an optimal \emph{dominating set}. We also consider the \emph{total} and \emph{paired} versions of both Min Vertex Cover and Min Dominating Set. We provide characterizations and linear time realization algorithms for all the above-mentioned problems. Since Min Paired Vertex Cover is closely related to Min Edge Dominating Set, our results for Degree Realization with respect to the former extend to the latter.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2611.06482 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:04.029Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).