Affiliations: Institute of Computer Science of PAS Ordona 21,
01-237, Warsaw, Poland. E-mail: Antoni.Mazurkiewicz@ipipan.waw.pl
Abstract: The paper deals with the class of finite triangular graphs. It turns
out that this class enjoys regular properties similar to those of trees and
complete graphs. The main objective of the paper is to lift algorithms for some
typical local computations, known for other classes of graphs, to the class of
triangular graphs. Local algorithms on graphs, according to [8, 9], are defined
as local rules for relabeling graph nodes. Rules are local, if they are defined
only for a class of subgraphs of processed graph (as neighborhoods of nodes or
edges) and neither their results nor their applicability do not depend upon the
knowledge of the whole graph labeling. While designing local algorithm for
triangular graphs one needs to use some intrinsic properties of such graphs; it
puts some additional light on their inherent structure. To illustrate essential
features of local computations on triangular graphs, local algorithms for three
typical issues of local computations are discussed: leader election, spanning
tree construction, and nodes ordering. Correctness of these algorithms, as
deadlock freeness, proper termination, and impartiality, are proved.
