Obtaining online ecological colourings by generalizing first-fit

DOI10.1007/S00224-013-9513-9zbMATH Open1380.68454OpenAlexW1989885684MaRDI QIDQ1678751FDOQ1678751

Viresh Patel, Daniël Paulusma, Théophile Trunck, Matthew Johnson

Publication date: 7 November 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/14140/1/14140.pdf

Recommendations

• Obtaining online ecological colourings by generalizing first-fit
• On-line and first fit colorings of graphs
• Publication:3496352
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
• scientific article

zbMATH Keywords

online algorithmsgraph homomorphismsgraph colouring

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Cites Work

• On the complexity of H-coloring
• The complexity of surjective homomorphism problems-a survey
• Role colouring a graph
• On-line coloring \(k\)-colorable graphs
• On-line and first fit colorings of graphs
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings

Uses Software

• STRUCTURE

This page was built for publication: Obtaining online ecological colourings by generalizing first-fit

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