Deterministic local algorithms, unique identifiers, and fractional graph colouring

DOI10.1016/J.TCS.2014.06.044zbMATH Open1332.68278OpenAlexW2175697336MaRDI QIDQ896700FDOQ896700

Authors: Henning Hasemann, Juho Hirvonen, Joel Rybicki, Jukka Suomela 

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

Recommendations

• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• On locally identifying coloring of graphs
• Locally identifying coloring of graphs
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• Locally identifying colourings for graphs with given maximum degree
• On the local colorings of graphs
• NP-completeness of local colorings of graphs
• scientific article; zbMATH DE number 2097236
• Locally identifying coloring in bounded expansion classes of graphs
• Local \(k\)-colorings of graphs and hypergraphs

zbMATH Keywords

distributed algorithmslocal algorithmsfractional domatic partitionfractional graph colouringunique identifiers

Mathematics Subject Classification ID

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

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• A note on the independence number of triangle-free graphs
• What cannot be computed locally!
• The Independence Ratio of Regular Graphs
• Local computation: lower and upper bounds
• Survey of local algorithms
• The price of being near-sighted
• Deterministic coin tossing with applications to optimal parallel list ranking
• What Can be Computed Locally?
• Deterministic local algorithms, unique identifiers, and fractional graph colouring
• Distributed maximal matching, greedy is optimal

Cited In (3)

• Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm
• Distributed algorithms for fractional coloring
• Deterministic local algorithms, unique identifiers, and fractional graph colouring

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

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