SAT ENCODINGS FOR BANDWIDTH COLORING: A SYSTEMATIC DESIGN STUDY

Duc Trung Kim Nguyen, Tuyen Van Kieu, Khanh Van To · 2026

Read SAT ENCODINGS FOR BANDWIDTH COLORING: A SYSTEMATIC DESIGN STUDY by Duc Trung Kim Nguyen, Tuyen Van Kieu, Khanh Van To (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-08423.txt.

Description

Assigning radio frequencies so neighbors stay far enough apart is a hard coloring problem with real spectrum stakes. Duc Trung Kim Nguyen and two co-authors systematically study how to encode bandwidth coloring for SAT solvers. Their arXiv paper tests six encodings in three families, plus incremental solving and symmetry breaking.

Encoding choices interact strongly with solver settings, and no single recipe wins everywhere. The unified framework reaches the best reported results on two benchmarks. Block encodings crack GEOM120b, the hardest case, to proven optimality in about a thousand seconds, where earlier methods failed within an hour. Readers get a design guide for exact frequency assignment.

Catalog record

CREATORDuc Trung Kim Nguyen, Tuyen Van Kieu, Khanh Van To
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-08423

Browse the full library · About the Tower of Babel