Deterministic local algorithms, unique identifiers, and fractional graph colouring

DOI10.1016/J.TCS.2014.06.044MaRDI QIDQ896700zbMATHOpenAlexFDO

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

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)

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

Cites work

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

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)