A fast heuristic for solving the D1EC coloring problem

Vincenzo Mancuso, Fabio Campoccia

    Research output: Contribution to conferenceOther


    In this paper we propose an efficient heuristic forsolving the Distance-1 Edge Coloring problem (D1EC) for theon-the-fly assignment of orthogonal wireless channels inwireless as soon as a topology change occurs. The coloringalgorithm exploits the simulated annealing paradigm, i.e., ageneralization of Monte Carlo methods for solvingcombinatorial problems. We show that the simulatedannealing-based coloring converges fast to a suboptimalcoloring scheme even for the case of dynamic channelallocation. However, a stateful implementation of the D1ECscheme is needed in order to speed-up the network coloringupon topology changes. In fact, a stateful D1EC reduces thealgorithm’s convergence time by more than 60% incomparison to stateless algorithms.
    Original languageEnglish
    Number of pages8
    Publication statusPublished - 2010

    Fingerprint Dive into the research topics of 'A fast heuristic for solving the D1EC coloring problem'. Together they form a unique fingerprint.

    Cite this