Fundamenta Informaticae - Volume 140, issue 2

Authors: Czerwiński, Wojciech | Gogacz, Tomasz | Kopczyński, Eryk

Article Type: Research Article

Abstract: We consider sequences of vectors from ℕd . Each coordinate of a vector can be reset or incremented by 1 with respect to the same coordinate of the preceding vector. We give an example of non-dominating sequence, like in Dickson’s Lemma, of length 22θ(n ) , what matches the previously known upper bound.

Keywords: Dickson’s Lemma

DOI: 10.3233/FI-2015-1247

Citation: Fundamenta Informaticae, vol. 140, no. 2, pp. 123-127, 2015

Authors: Ryszka, Iwona | Paszyńska, Anna | Grabska, Ewa | Sieniek, Marcin | Paszyński, Maciej

Article Type: Research Article

Abstract: In this paper we present several graph transformation systems modeling three dimensional h -adaptive Finite Element Method (3D h -FEM) algorithms with tetrahedral finite elements. In our approach a computational mesh is represented by a composite graph and mesh operations are expressed by the graph transformation rules. Each graph transformation system is responsible for different kind of operations. In particular, there is a graph transformation system expressing generation of an initial mesh, generating element matrices and elimination trees for interfacing with direct solver algorithm, a graph transformation system deciding which elements have to be further refined, as well as a …graph transformation system responsible for execution of mesh refinements. These graph transformation systems are tested using a graph transformation tool (called GRAGRA), which provides a graphical environment for defining graphs, graph transformation rules and graph transformation systems. In this paper we illustrate the concepts by using an exemplary derivation for a three dimensional projection problem, based on a set of graph transformation rules. Show more

Keywords: Graph transformation system, Automatic h adaptivity, Finite Element Method

DOI: 10.3233/FI-2015-1248

Citation: Fundamenta Informaticae, vol. 140, no. 2, pp. 129-172, 2015

Authors: Ryszka, Iwona | Paszyńska, Anna | Grabska, Ewa | Sieniek, Marcin | Paszyński, Maciej

Article Type: Research Article

Abstract: In this paper we introduce formal definitions for several graph transformation systems modeling three dimensional h -adaptive Finite Element Method (3D h -FEM) algorithms with tetrahedral finite elements. We introduce a composite graph representation of the computational mesh and graph transformation rules expressing the mesh operations. In particular, there are graph transformation rules expressing the generation of the initial mesh consisting with tetrahedral finite elements, graph transformation rules expressing the construction of an elimination tree for interfacing with multi-frontal direct solver algorithm, graph transformation rules selecting sub-graph representing finite elements for further refinements, graph transformation rules responsible for execution of …mesh refinements. We also discuss several benefits of using graph transformation system instead of classical FEM approach, including the benefits from the viewpoint of multi-frontal direct solvers. Show more

Keywords: Graph transformation system, Automatic h adaptivity, Finite Element Method

DOI: 10.3233/FI-2015-1249

Citation: Fundamenta Informaticae, vol. 140, no. 2, pp. 173-203, 2015

Authors: Akbari Torkestani, Javad

Article Type: Research Article

Abstract: In this paper, a learning automata-based algorithm is proposed for approximating a near optimal solution to the bounded diameter minimum spanning tree (BDMST) problem in stochastic graphs. A stochastic graph is a graph in which the weight associated with each edge is a random variable. Stochastic BDMST problem seeks for finding the BDMST in a stochastic graph. To the best of our knowledge, no work has been done on solving the stochastic BDMST problem, where the weight associated with the graph edge is random variable. In this study, we assume that the probability distribution of the edges random weight is …unknown a priori. This makes the stochastic BDMST problem incredibly hard-to-solve. To show the efficiency of the proposed algorithm, its results are compared with those of the standard sampling method (SSM). Numerical results show the superiority of the proposed sampling algorithm over the SSM both in terms of the sampling rate and convergence rate. Show more

Keywords: Bounded diameter minimum spanning tree problem, stochastic graph, learning automata, sampling

DOI: 10.3233/FI-2015-1250

Citation: Fundamenta Informaticae, vol. 140, no. 2, pp. 205-219, 2015