Vertex coloring of a graph for memory constrained scenarios

DOI10.1007/S11786-019-00409-4MaRDI QIDQ2183733zbMATH OpenOpenAlexWikidataFDO

Authors Eduardo Sant'Ana da Silva, Helio Pedrini

Publication date 27 May 2020

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11786-019-00409-4

zbMATH Keywords

approximation algorithmchromatic numbervertex coloringlimited resource devices

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Parameterized complexity of vertex colouring
• An exact approach for the vertex coloring problem
• Vertex coloring of graphs with few obstructions
• Efficient constraint propagation for graph coloring
• The vertex coloring problem and its generalizations
• A new approach to the vertex coloring problem
• Vertex coloring with communication and local memory constraints in synchronous broadcast networks
• scientific article; zbMATH DE number 3876617
• An incremental search heuristic for coloring vertices of a graph

Cites work

• scientific article; zbMATH DE number 3968611 (Why is no real title available?)
• scientific article; zbMATH DE number 1306877 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 6850309 (Why is no real title available?)
• scientific article; zbMATH DE number 1830756 (Why is no real title available?)
• A Parallel Graph Coloring Heuristic
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A course in combinatorics.
• A fast parallel coloring of planar graphs with five colors
• A framework for scalable greedy coloring on distributed-memory parallel computers
• A note on the complexity of the chromatic number problem
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Dynamic graph coloring
• Enumerating maximal independent sets with applications to graph colouring.
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Finding a Maximum Independent Set
• Formal proof - the four color theorem
• Graph theory with applications
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• Local antimagic vertex coloring of a graph
• NP-completeness of a family of graph-colouring problems
• New methods to color the vertices of a graph
• Online graph coloring against a randomized adversary
• Spectrum graph coloring and applications to Wi-Fi channel assignment
• Sur le coloriage des graphs
• The greedy coloring is a bad probabilistic algorithm
• The smallest hard-to-color graph for algorithm DSATUR
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Uncertain vertex coloring problem
• Vertex coloring of graphs with few obstructions

Cited in

(3)

• Hypergraph coloring and reconfigured RAM testing
• An adaptive memory algorithm for the k-coloring problem
• Vertex coloring with communication and local memory constraints in synchronous broadcast networks

Describes a project that uses

Uses Software

• DSATUR

This page was built for publication: Vertex coloring of a graph for memory constrained scenarios

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2183733)