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

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Normalize DOI.
 
(4 intermediate revisions by 4 users not shown)
Property / DOI
 
Property / DOI: 10.3390/sym10030065 / rank
Normal rank
 
Property / OpenAlex ID
 
Property / OpenAlex ID: W3101652746 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1602.05038 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient location of resources in cylindrical networks / rank
 
Normal rank
Property / cites work
 
Property / cites work: A survey on vertex coloring problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Models and solution techniques for frequency assignment problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bandwidth allocation in cellular networks with multiple interferences / rank
 
Normal rank
Property / cites work
 
Property / cites work: Weighted improper colouring / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph labellings with variable weights, a survey / rank
 
Normal rank
Property / cites work
 
Property / cites work: Distance Coloring / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4501549 / rank
 
Normal rank
Property / cites work
 
Property / cites work: \(T\)-colorings of graphs: recent results and open problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Dichotomies properties on computational complexity of \(S\)-packing coloring problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A generalization of edge-coloring in graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On total rainbow \(k\)-connected graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: New methods to color the vertices of a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4142699 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3035307 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A range-compaction heuristic for graph coloring / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph coloring with adaptive evolutionary algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new \textsf{DSATUR}-based algorithm for exact vertex coloring / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5687246 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Random graph models of social networks / rank
 
Normal rank
Property / cites work
 
Property / cites work: A DSATUR-based algorithm for the equitable coloring problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: A comprehensive survey on particle swarm optimization algorithm and its applications / rank
 
Normal rank
Property / Wikidata QID
 
Property / Wikidata QID: Q130120557 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.3390/SYM10030065 / rank
 
Normal rank

Latest revision as of 01:25, 11 December 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
    0 references
    0 references
    0 references