Metraipolis › archive › dc_5d8ddbbf1d7c

Degree Realization with Maximum Matching — arXiv:2610.41810

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41810
License (as archived)
CC0-1.0
Archived
2026-11-03T05:49:26.212Z
SHA-256 of the archived text
71bc8440e864bbd9101f0bc803b22c2c5e8c12228426b81606010629a2b0f5a3
Stable URL of this page
https://metraipolis.com/documento/dc_5d8ddbbf1d7c

How to cite

Degree Realization with Maximum Matching — arXiv:2610.41810 — arXiv (en), https://arxiv.org/abs/2610.41810 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5d8ddbbf1d7c (Metraipolis archive dc_5d8ddbbf1d7c, sha256 71bc8440e864bbd9101f0bc803b22c2c5e8c12228426b81606010629a2b0f5a3)
BibTeX
@misc{dc5d8ddbbf1d7c,
  title = {Degree Realization with Maximum Matching — arXiv:2610.41810},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41810},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5d8ddbbf1d7c; sha256 71bc8440e864bbd9101f0bc803b22c2c5e8c12228426b81606010629a2b0f5a3},
  year = {2026}
}

Archived text

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

The Maximum Matching Degree Realization problem requires, for a sequence $d$ of $n$ positive integers, to compute a realizing graph(whose degree sequence corresponds to $d$) with the maximum possible matching. We present a polynomial-time algorithm for this problem. The decision version of this problem requires to determine whether a sequence $d$ admits a realization with a matching of size $\nu$ (without computing such a realization). Recently, it was shown that it can be done by verifying a series of inequalities. We improve the existing characterization by reducing the number of inequalities.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.41810 — 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-03T05:34:47.030Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).