Sökning: "graffärgning"

Hittade 3 uppsatser innehållade ordet graffärgning.

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

   Kandidat-uppsats, KTH/Skolan för elektroteknik och datavetenskap (EECS)

   Författare :Adrian Salamon; Klara Sandström; [2023]
   Nyckelord :;

   Sammanfattning : 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. LÄS MER

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

   Kandidat-uppsats, KTH/Datavetenskap

   Författare :Samuel Falk; Erik Nordlöf; [2022]
   Nyckelord :;

   Sammanfattning : 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. LÄS MER

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

   Kandidat-uppsats, Linköpings universitet/Matematik och tillämpad matematik; Linköpings universitet/Tekniska fakulteten

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

   Sammanfattning : 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. LÄS MER