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

Spanning graphs and the Axiom of Choice

Delhommi Ch., Morillon M.

Reports on Mathematical Logic

|

2006

|

Nr 40

165-180

EN

We show in set-theory ZF that the axiom of choice is equivalent to the statement every bipartite connected graph has a spanning sub-graph omitting some complete finite bipartite graph Kn;n, and in particular it is equivalent to the fact that every connected graph has a spanning cycle-free graph (possibly non connected).

3

Extensions of the minimum labelling spanning tree problem

Cerulli R., Fink A., Gentili M., Voss S.

Journal of Telecommunications and Information Technology

|

2006

|

nr 4

39-45

EN

In this paper we propose some extensions of the minimum labelling spanning tree problem. The main focus is on the minimum labelling Steiner tree problem: given a graph G with a color (label) assigned to each edge, and a subset Q of the nodes of G (basic vertices), we look for a connected subgraph of G with the minimum number of different colors covering all the basic vertices. The problem has several applications in telecommunication networks, electric networks, multimodal transportation networks, among others, where one aims to ensure connectivity by means of homogeneous connections. Numerical results for several metaheuristics to solve the problem are presented.

4

Ordered graphs and minimal spanning trees

Schweigert D.

Foundations of Computing and Decision Sciences

|

1999

|

Vol. 24, No. 4

219-229