Useful names for vertices: An introduction to dynamic implicit informative labelling schemes

• Author(s) / Creator(s)

  • Morgan, David

• Technical report TR05-04. As defined by Peleg (Peleg, LNCS vol. 1893, 2000), an informative labelling scheme labels the vertices of a graph so that information can be deduced from the vertex labels. Peleg's paper on informative labelling schemes generalized the concepts introduced by Muller (Muller, Ph.D. thesis, Georgia Tech, 1988) and Kannan et al. (Kannan et al., SIAM J Disc Math, 1992) in which the adjacency of two vertices could be determined using only their labels. In general, the vertex labellings used in informative labelling schemes cannot be tweaked to accommodate small changes in the graph. Although Kannan et al., suggested the dynamic version of their problem as a direction for future research, only one paper has explored this topic. The paper of Brodal and Fagerberg (Brodal and Fagerberg, LNCS vol. 1663, 1999) devises a dynamic scheme for graphs of bounded arboricity, however, it lacks a formal statement of the dynamic problem. Motivated by the necessity of such a formal statement, we define the notion of a dynamic implicit informative labelling scheme; discuss measures for judging the quality of such dynamic schemes; and show a connection between the existence of dynamic schemes and the recognition problem. To illustrate the concept of a dynamic implicit informative labelling scheme we develop a space-optimal dynamic implicit adjacency labelling scheme for r-minoes; as per the definition of Metelsky and Tyshkevich (Metelsky and Tyshkevich, SIAM J Disc Math, 2003), a graph is said to be an r-mino if none of its vertices belong to more than r maximal cliques. | TRID-ID TR05-04

• Date created

  2005

• Subjects / Keywords

  • $r$-mino
  • Dynamic implicit informative labelling scheme
  • Implicit representation

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3BJ9W

• License

  Attribution 3.0 International