Metraipolis › archive › dc_de75ff42dc50

Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems — arXiv:2609.20091

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.20091
License (as archived): CC0-1.0
Archived: 2026-10-10T03:21:43.053Z
SHA-256 of the archived text: c6ec407f14409a223695e903bac47df423fca11f272b0e471b44551bdbf93579
Stable URL of this page: https://metraipolis.com/documento/dc_de75ff42dc50

How to cite

Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems — arXiv:2609.20091 — arXiv (en), https://arxiv.org/abs/2609.20091 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_de75ff42dc50 (Metraipolis archive dc_de75ff42dc50, sha256 c6ec407f14409a223695e903bac47df423fca11f272b0e471b44551bdbf93579)

BibTeX

@misc{dcde75ff42dc50,
  title = {Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems — arXiv:2609.20091},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20091},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_de75ff42dc50; sha256 c6ec407f14409a223695e903bac47df423fca11f272b0e471b44551bdbf93579},
  year = {2026}
}

Archived text

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

The Antibandwidth and Cyclic Antibandwidth problems are NP-hard graph labeling problems that aim to maximize the minimum (cyclic) distance between labels assigned to adjacent vertices. Extensive research on these problems has resulted in a variety of mathematical formulations and computational approaches. However, their minimum span perspective, in which a prescribed minimum (cyclic) distance is fixed and the objective is to minimize the label span, has received comparatively little attention. In this paper, we consider this complementary perspective by introducing the Minimum Span Antibandwidth/Cyclic Antibandwidth Labeling (MSABL/MSCABL) problems and developing a unified Boolean Satisfiability (SAT)-based framework for solving them. The SAT-based framework formulates MSABL/MSCABL as a sequence of decision problems and exploits their monotonicity to accelerate the search process. We also consider two SAT solving strategies, parallel and incremental SAT solving: the former examines multiple candidate spans concurrently, while the latter reuses a single SAT instance while progressively restricting the label domain. The proposed approaches are evaluated on benchmark instances from the Harwell-Boeing Sparse Matrix Collection and compared with CPLEXCP, CPLEXMIP, and Gurobi. The results show that SAT-based approaches are highly competitive in solution quality, with the parallel approach performing best overall for MSCABL and the incremental approach for MSABL. With the no-hole constraint, they remain competitive with CPLEXCP and significantly outperform CPLEXMIP and Gurobi, particularly for MSCABL. These results demonstrate the effectiveness of SAT solving as an exact approach for MSABL and MSCABL.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-18 in cs.AI).
Categorie arXiv: Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2609.20091 — 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-10-10T03:04:13.708Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).