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

DOI10.1002/NET.20432zbMATH Open1233.05172OpenAlexW2024403359MaRDI QIDQ3100700FDOQ3100700

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Classification of distributed binary labeling problems
• Packing bipartite graphs with covers of complete bipartite graphs
• 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)