Advanced search

Found 3 essays matching the above criteria.

1. 1. 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

3. 2. 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

4. 3. Upper bounds on the star chromatic index for bipartite graphs

   University essay from Linköpings universitet/Matematik och tillämpad matematik; Linköpings universitet/Tekniska fakulteten

   Author : Victor Melinder; [2020]
   Keywords : Graph Theory; Star edge colouring; Star chromatic index; Graph colouring; Biregular; Graph; Grafteori; stjärnkantsfärgning; stjärnkromatiskt index; graffärgning; Bireguljär; Graf;

   Abstract : An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. READ MORE