Essays about: "Graph coloring"

Showing result 1 - 5 of 14 essays containing the words Graph coloring.

  1. 1. Comparing Quantum Annealing and Simulated Annealing when Solving the Graph Coloring Problem

    University essay from KTH/Skolan för elektroteknik och datavetenskap (EECS)

    Author : Nora Odelius; Isak Reinholdsson; [2023]
    Keywords : Quantum Computing; Quantum Annealing; Simulated Annealing; Graph Coloring Problem; Kvantberäkningar; Quantum Annealing; Simulated Annealing; Graffärgningsproblemet;

    Abstract : Quantum annealing (QA) is an optimization process in quantum computing similar to the probabilistic metaheuristic simulated annealing (SA). The QA process involves encoding an optimization problem into an energy landscape, which it then traverses in search for the point of minimal energy representing the global optimal state. READ MORE

  3. 2. Reinforcement learning for improved local search : Applied to the graph coloring problem

    University essay from KTH/Skolan för elektroteknik och datavetenskap (EECS)

    Author : Adrian Salamon; Klara Sandström; [2023]
    Keywords : ;

    Abstract : The graph coloring problem (GCP) is an important combinatorial optimization problem (COP) with various applications and a simple formulation: to assign colors to vertices in a graph such that no adjacent vertices share a color. The GCP is NP-hard, and in order to solve it within a reasonable time frame, heuristic local search (LS) based algorithms are commonly used. READ MORE

  4. 3. Discrete Flower Pollination Algorithm for the Graph Coloring Problem

    University essay from KTH/Datavetenskap

    Author : Samuel Falk; Erik Nordlöf; [2022]
    Keywords : ;

    Abstract : The graph coloring problem (GCP) is a famous NP-hard problem applicable to many real-world problems. The Flower Pollination Algorithm (FPA) is a relatively recently developed algorithm based on the pollination-behaviors of flowers. It has seen great results in single- and multi-objective optimization in continuous search spaces. READ MORE

  5. 4. Upper bounds for the star chromatic index of multipartite graphs

    University essay from Linköpings universitet/Algebra, geometri och diskret matematik; Linköpings universitet/Tekniska fakulteten

    Author : Gabriel Sparrman; [2022]
    Keywords : Graph; Graph theory; Multipartite Graph; Graph Coloring; Star edge coloring; Star chromatic index;

    Abstract : A star edge coloring is any edge coloring which is both proper and contains no cycles or path of length four which are bicolored, and the star chromatic index of a graph is the smallest number of colors for which that graph can be star edge colored. Star edge coloring is a relatively new field in graph theory, and very little is known regarding upper bounds of the star chromatic index of most graph types, one of these families being multipartite graphs. READ MORE

  6. 5. Finding Locally Unique IDs in Enormous IoT systems

    University essay from Luleå tekniska universitet/Institutionen för system- och rymdteknik

    Author : Sebastian Yngman; [2022]
    Keywords : IoT; Internet of Things; Graph Coloring; Optimization;

    Abstract : The Internet of Things (IoT) is an important and expanding technology used for a large variety of applications to monitor and automate processes. The aim of this thesis is to present a way to find and assign locally unique IDs to access points (APs) in enormous wireless IoT systems where mobile tags are traversing the network and communicating with multiple APs simultaneously. READ MORE