Wyniki wyszukiwania - BazTech

1

Local Computations on Triangular Graphs

Mazurkiewicz A.

Fundamenta Informaticae

|

2010

|

Vol. 100, nr 1/4

117-140

EN

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.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.

2

Compositional Systems over Reducible Networks - invited paper

Mazurkiewicz A.

Fundamenta Informaticae

|

2007

|

Vol. 79, nr 3-4

265-282

EN

In the paper two notions related to local (distributed) computations are identified and discussed. The first one is the notion of reducible graphs. A graph is reducible if it can be reduced to a singleton by successive removing its removable nodes; the removing procedure should be local in the sense that to decide whether a node is removable or not it is sufficient to inspect its neighborhood. The second is the notion of compositional systems, consisting of a set of objects together with a composition operation which to each pair of local objects (like local votes, partial trees, partial orderings, local consensus, local processes etc.) assigns their possible compositions; a sequence of such composition operations leads to a global object (like a global vote, a full spanning tree, a total ordering, a global consensus, a synchronized process, etc). Combining these two notions gives rise to a generic distributed algorithm for composing different local objects assigned to nodes of a reducible graph into one global object assigned to all nodes. Correctness of the composing algorithm, i.e its proper termination and its impartiality is proved.

3

In-water remote sensing algorithms for the detection of chlorophyll and yellow substances in the Pomeranian Bay

Olszewski J., Kowalczuk P., Darecki M.

Oceanologia

|

1999

|

No. 41 (3)

461-474

EN

In-water remote sensing algorithms for estimating chlorophyll concentration and the absorption of light (400 nm) by yellow substances valid for the surface layer of the Pomeranian Bay are described. The accuracy of the algorithms has been estimated at 20-60%. The statistical analysis of data collected during a two-year experiment in 1996-1997 enable algorithms to be constructed which use a linear combination of spectral reflectances at selected wavelengths, all of them in the log-log form. The wavelengths in nm are 510, 550, 589 or 510, 625 in the 'chlorophyll' case, and 589, 665 or 490, 665 in the 'yellow substances' case. The correlation coefficient between the log-transformed reflectance ratios and the chlorophyll concentration is around 0.9. The correlation coefficient between the log-transformed reflectance ratios and the yellow substance absorption coefficient at λ= 400 nm is around 0.6.