Spectrum graph coloring and applications to Wi-Fi channel assignment

DOI10.3390/SYM10030065MaRDI QIDQ1657008zbMATH OpenOpenAlexWikidataFDO

Authors David Orden, Jose Manuel Gimenez-Guzman, Ivan Marsa-Maestre, Enrique de la Hoz

Publication date 13 August 2018

Published in Symmetry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1602.05038

zbMATH Keywords

chromatic numberDSATURfrequency assignmentgraph coloringinterferenceWi-Fi channel assignment

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Applications of graph theory (05C90) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 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.

Review text

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.

Recommendations

• Bounds on spectrum graph coloring
• Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction
• Soft Edge Coloring
• Weighted Improper Colouring
• Channel Dependent Interference and Decentralized Colouring

Cites work

• \(T\)-colorings of graphs: recent results and open problems
• A comprehensive survey on particle swarm optimization algorithm and its applications
• A DSATUR-based algorithm for the equitable coloring problem
• A generalization of edge-coloring in graphs
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• A range-compaction heuristic for graph coloring
• A survey on vertex coloring problems
• Bandwidth allocation in cellular networks with multiple interferences
• Dichotomies properties on computational complexity of S-packing coloring problems
• Distance Coloring
• Efficient location of resources in cylindrical networks
• Graph coloring with adaptive evolutionary algorithms
• Graph labellings with variable weights, a survey
• scientific article; zbMATH DE number 4134069 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1500531 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• Models and solution techniques for frequency assignment problems
• New methods to color the vertices of a graph
• On total rainbow \(k\)-connected graphs
• Random graph models of social networks
• Weighted improper colouring

Cited in

(8)

• Maximum scan statistics and channel assignment problems in homogeneous wireless networks
• Vertex coloring of a graph for memory constrained scenarios
• Contrast in greyscales of graphs
• Spectrum graph coloring to improve Wi-Fi channel assignment in a real-world scenario via edge contraction
• Channel Dependent Interference and Decentralized Colouring
• A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem
• Bounds on spectrum graph coloring
• Coloring of graphs associated with commutative rings

Describes a project that uses

Uses Software

• CALMA
• DIMACS

This page was built for publication: Spectrum graph coloring and applications to Wi-Fi channel assignment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1657008)