Vertex coloring of a graph for memory constrained scenarios
type: Item
instance of: scholarly article
title: Vertex coloring of a graph for memory constrained scenarios
zbMATH Open document ID: 1455.68148
author: Eduardo Sant'Ana da Silva
author: Helio Pedrini
published in: Mathematics in Computer Science
publication date: 2020-05-27T00:00:00Z
review text: A (proper) \(k\)-\textit{vertex coloring} of an undirected graph \(G=(V, E)\) with colors \(C = \{c_1, \dots, c_k\}\) is a function \(\phi : V \to C\) for which \(\phi(a) \neq \phi(b)\) whenever \(\{a,b\} \in E\). A graph \(G\) is \(k\)-\textit{colorable} when it admits a \(k\)-vertex coloring. The \textit{chromatic number} of \(G\) is the smallest \(k\) for which \(G\) is \(k\)-colorable. When \(k \geq 3\), it is NP-complete to decide whether a graph is \(k\)-colorable. Because vertex coloring has numerous practical applications such as resource scheduling, compiler register allocation, pattern matching, puzzle solving, and exam timetabling, efficient algorithms to approximate the chromatic number have been developed. In this paper, a need is identified for approximation methods that are suitable for memory-constrained microprocessors with limited instruction sets, such as sensors. A heuristic vertex coloring method is proposed that uses simple operations and limited storage. Computational results are shown to illustrate the effectiveness of the proposed method.
reviewed by: Charles J. Colbourn
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7205382
zbMATH Keywords: vertex coloring
zbMATH Keywords: chromatic number
zbMATH Keywords: approximation algorithm
zbMATH Keywords: limited resource devices
describes a project that uses: DSATUR
MaRDI profile type: MaRDI publication profile
full work available at URL: s11786-019-00409-4
OpenAlex ID: W2973445334
cites work: Local antimagic vertex coloring of a graph
cites work: Dynamic graph coloring
cites work: Q4252729
cites work: Q4607872
cites work: Q4398864
cites work: A framework for scalable greedy coloring on distributed-memory parallel computers
cites work: Q3097395
cites work: Three-coloring and list three-coloring of graphs without induced paths on seven vertices
cites work: New methods to color the vertices of a graph
cites work: Online Graph Coloring Against a Randomized Adversary
cites work: Enumerating maximal independent sets with applications to graph colouring.
cites work: Uncertain vertex coloring problem
cites work: Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
cites work: Q3735725
cites work: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
cites work: Q4778579
cites work: Q5302559
cites work: NP-completeness of a family of graph-colouring problems
cites work: The smallest hard-to-color graph for algorithm DSATUR
cites work: A Parallel Graph Coloring Heuristic
cites work: The greedy coloring is a bad probabilistic algorithm
cites work: A note on the complexity of the chromatic number problem
cites work: A course in combinatorics.
cites work: Vertex coloring of graphs with few obstructions
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: Sur le coloriage des graphs
cites work: A fast parallel coloring of planar graphs with five colors
cites work: Spectrum graph coloring and applications to Wi-Fi channel assignment
cites work: Finding a Maximum Independent Set
cites work: An upper bound for the chromatic number of a graph and its application to timetabling problems
cites work: Q4414647
Wikidata QID: Q127225979
DOI: 10.1007/S11786-019-00409-4
Recommended article: Parameterized complexity of vertex colouring
Recommended article: An exact approach for the vertex coloring problem
Recommended article: Vertex coloring of graphs with few obstructions
Recommended article: Efficient constraint propagation for graph coloring
Recommended article: The vertex coloring problem and its generalizations
Recommended article: A NEW APPROACH TO THE VERTEX COLORING PROBLEM
Recommended article: Vertex coloring with communication and local memory constraints in synchronous broadcast networks
Recommended article: Q3341922
Recommended article: An incremental search heuristic for coloring vertices of a graph
description: scientific article; zbMATH DE number 7205382