On distance graph coloring problems

Rosiane de Freitas

doi:10.1111/itor.12626

On distance graph coloring problems

2019-01-21

6

PRE

AI

DOI：10.1111/itor.12626

Original

Original request for help

Save

Abstract

En 中文

One of the most important classes of combinatorial optimization problems is graph coloring, and there are several variations of this general problem involving additional constraints either on vertices or edges. They constitute models for real applications, such as channel assignment in mobile wireless networks. In this work, we consider some coloring problems involving distance constraints as weighted edges, modeling them as distance geometry problems (DGPs). Thus, the vertices of the graph are considered as embedded on the real line and the coloring is treated as an assignment of positive integers to the vertices, while the distances correspond to line segments, where the goal is to find their feasible intersection. We formulate these coloring problem variants and show feasibility conditions for some problems. We also propose implicit enumeration methods for some of the optimization problems based on branch-and-prune algorithms proposed for DGPs in the literature. An empirical analysis was undertaken, considering equality and inequality constraints, and uniform and arbitrary set of distances. As the main contributions, we propose new variations of vertex coloring problems in graphs, involving a new theoretical model in distance geometry (DG) for vertex coloring problems with generalized adjacency constraints, promoting the correlation between graph theory and DG fields. We also give a characterization and formal proof of polynomial cases for special graph classes, since the general main problem is NP-complete.

Keywords:

algorithms

bandwidth coloring

computational complexity

distance geometry

graph theory

T‐ coloring

On distance graph coloring problems

Abstract

AI Summary

Journal

Organization