Improved self-stabilizing algorithms for L(2, 1)-labeling tree networks

DOI10.1007/S11786-011-0081-6MaRDI QIDQ691628zbMATH OpenOpenAlexFDO

Authors Pranay Chaudhuri, Hussein Thompson

Publication date 3 December 2012

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11786-011-0081-6

zbMATH Keywords

1)\)-labeling\(L(2complexitydistributed systemgraph coloringself-stabilizing algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• A linear time algorithm for L(2,1)-labeling of trees
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• An efficient self-stabilizing distance-2 coloring algorithm

Cites work

• \(L(h,1)\)-labeling subclasses of planar graphs
• A dynamic self-stabilizing algorithm for constructing a transport net
• A self-stabilizing algorithm for coloring bipartite graphs
• A self-stabilizing algorithm for coloring planar graphs
• A self-stabilizing algorithm for constructing breadth-first trees
• A self-stabilizing algorithm for constructing spanning trees
• A self-stabilizing algorithm for detecting fundamental cycles in a graph
• A self-stabilizing algorithm for maximal matching
• Approximations for  -Colorings of Graphs
• scientific article; zbMATH DE number 1185300 (Why is no real title available?)
• scientific article; zbMATH DE number 1760042 (Why is no real title available?)
• scientific article; zbMATH DE number 1863300 (Why is no real title available?)
• Labeling trees with a condition at distance two.
• Labelling Graphs with a Condition at Distance 2
• Linear time self-stabilizing colorings
• On \(L(d,1)\)-labelings of graphs
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
• Self-stabilizing depth-first search
• Self-stabilizing systems in spite of distributed control
• The $L(2,1)$-Labeling Problem on Graphs

Cited in

(1)

• Self-stabilizing labeling and ranking in ordered trees

This page was built for publication: Improved self-stabilizing algorithms for \(L(2, 1)\)-labeling tree networks

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