Graph labelings derived from models in distributed computing: A complete complexity classification

DOI10.1002/NET.20432MaRDI QIDQ3100700zbMATH OpenOpenAlexFDO

Authors J. Chalopin, Daniël Paulusma

Publication date 21 November 2011

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20432

zbMATH Keywords

computational complexitygraph homomorphismleader electionlocal computationgraph labelingmessage-passingnaming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Graph Labelings Derived from Models in Distributed Computing
• Local computations in graphs: the case of cellular edge local computations
• Graph Transformations
• SOFSEM 2005: Theory and Practice of Computer Science

Cites work

• scientific article; zbMATH DE number 5286867 (Why is no real title available?)
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 2104616 (Why is no real title available?)
• scientific article; zbMATH DE number 2111730 (Why is no real title available?)
• A complete complexity classification of the role assignment problem
• Complexity of hypergraph coloring and Seidel's switching.
• Covering regular graphs
• Distributed enumeration
• Fibrations of graphs
• Foundations of Software Science and Computation Structures
• Graph theory with applications
• Introduction to Distributed Algorithms
• Local computations in graphs: the case of cellular edge local computations
• Locally constrained graph homomorphisms and equitable partitions
• Packing bipartite graphs with covers of complete bipartite graphs
• Partial covers of graphs
• Paths, Trees, and Flowers
• SOFSEM 2005: Theory and Practice of Computer Science

Cited in

(9)

• Graph Labelings Derived from Models in Distributed Computing
• Graph covers: where topology meets computer science, and simple means difficult
• An algorithmic framework for locally constrained homomorphisms
• scientific article; zbMATH DE number 6456807 (Why is no real title available?)
• Packing bipartite graphs with covers of complete bipartite graphs
• Classification of distributed binary labeling problems
• An algorithmic framework for locally constrained homomorphisms
• Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
• The computational complexity of cordial and equitable labelling

This page was built for publication: Graph labelings derived from models in distributed computing: A complete complexity classification

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