Uncertain vertex coloring problem

Lin Chen

doi:10.1007/s00500-017-2861-7

Uncertain vertex coloring problem

2017-10-20

6

PRE

AI

DOI：10.1007/s00500-017-2861-7

Original

Original request for help

Save

Abstract

En 中文

This paper investigates the vertex coloring problem in an uncertain graph in which all vertices are deterministic, while all edges are not deterministic and exist with some degree of belief in uncertain measures. The concept of the maximal uncertain independent vertex set of an uncertain graph is first introduced. We then present a degree of belief rule to obtain the family of maximal uncertain independent vertex sets. Based on the maximal uncertain independent vertex set, some properties of the separation degree of an uncertain graph are discussed. Following that, the concept of an uncertain chromatic set is introduced. Then, a maximum separation degree algorithm is derived to obtain the uncertain chromatic set. Finally, numerical examples are presented to demonstrate the application of the vertex coloring problem in uncertain graphs and the effectiveness of the maximum separation degree algorithm.

Keywords:

Vertex coloring problem

Uncertain graph

Maximal uncertain independent vertex set

Degree of belief rule

Uncertain chromatic set

Maximum separation degree algorithm

Uncertain vertex coloring problem

Abstract

AI Summary

Journal

Organization