Deterministic local algorithms, unique identifiers, and fractional graph colouring

DOI10.1016/j.tcs.2014.06.044zbMath1332.68278OpenAlexW2175697336MaRDI QIDQ896700

Henning Hasemann, Jukka Suomela, Joel Rybicki, Juho Hirvonen

Publication date: 10 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.06.044

zbMATH Keywords

distributed algorithmslocal algorithmsfractional domatic partitionfractional graph colouringunique identifiers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Distributed algorithms (68W15) Fractional graph theory, fuzzy graph theory (05C72)

Related Items (2)

Node labels in local decision ⋮ Distributed algorithms for fractional coloring

Cites Work

• A note on the independence number of triangle-free graphs
• Survey of local algorithms
• Deterministic Local Algorithms, Unique Identifiers, and Fractional Graph Colouring
• Distributed maximal matching
• Lower bounds for local approximation
• Local Computation
• The price of being near-sighted
• Deterministic coin tossing with applications to optimal parallel list ranking
• The Independence Ratio of Regular Graphs
• Distributed Computing: A Locality-Sensitive Approach
• What Can be Computed Locally?
• What cannot be computed locally!

This page was built for publication: Deterministic local algorithms, unique identifiers, and fractional graph colouring