Vertex coloring of a graph for memory constrained scenarios

DOI10.1007/S11786-019-00409-4zbMATH Open1455.68148OpenAlexW2973445334WikidataQ127225979 ScholiaQ127225979MaRDI QIDQ2183733FDOQ2183733

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

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

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)

Cites Work

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

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

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)