Spectrum graph coloring and applications to Wi-Fi channel assignment (Q1657008): Difference between revisions

From MaRDI portal
Changed an Item
Changed an Item
Property / describes a project that uses
 
Property / describes a project that uses: DIMACS / rank
 
Normal rank

Revision as of 07:46, 29 February 2024

scientific article
Language Label Description Also known as
English
Spectrum graph coloring and applications to Wi-Fi channel assignment
scientific article

    Statements

    Spectrum graph coloring and applications to Wi-Fi channel assignment (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    13 August 2018
    0 references
    Summary: We introduce and explore a family of vertex-coloring problems, which, surprisingly enough, have not been considered before despite stemming from the problem of Wi-Fi channel assignment. Given a spectrum of colors, endowed with a matrix of interferences between each pair of colors, the Threshold Spectrum Coloring problem fixes the number of colors available and aims to minimize the interference threshold, i.e., the maximum of the interferences at the vertices. Conversely, the Chromatic Spectrum Coloring problem fixes a threshold and aims to minimize the number of colors for which respecting that threshold is possible. As the main theoretical results, we prove tight upper bounds for the solutions to each problem. Since both problems turn out to be NP-hard, we complete the scene with experimental results. We propose a DSATUR-based heuristic and study its performance to minimize the maximum vertex interference in Wi-Fi channel assignment, both for randomly-generated graphs and for a real-world scenario. Further, for all these graphs, we experimentally check the goodness of the theoretical bounds.
    0 references
    graph coloring
    0 references
    interference
    0 references
    chromatic number
    0 references
    DSATUR
    0 references
    frequency assignment
    0 references
    Wi-Fi channel assignment
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references