Fundamenta Informaticae - Volume 114, issue 2

Authors: Borowiecki, Piotr | Sidorowicz, Elżbieta

Article Type: Research Article

Abstract: Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm's input during the coloring process. …Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problem of dynamic coloring with discoloring constraints for which the performance of the dynamic algorithm Time-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors. Show more

Keywords: graph coloring, greedy coloring, Grundy number, critical graphs, algorithms, trees, graph product

DOI: 10.3233/FI-2012-620

Citation: Fundamenta Informaticae, vol. 114, no. 2, pp. 105-128, 2012

Authors: Herman, Grzegorz | Soltys, Michael

Article Type: Research Article

Abstract: We investigate different variants of unambiguity in the context of computing multi-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.

Keywords: Logarithmic Space, Nondeterminism, Reduction, Unambiguity

DOI: 10.3233/FI-2012-621

Citation: Fundamenta Informaticae, vol. 114, no. 2, pp. 129-147, 2012

Authors: Paszyńska, Anna | Grabska, Ewa | Paszyński, Maciej

Article Type: Research Article

Abstract: The first part of our paper presents a composite programmable graph grammar model for the self-adaptive two dimensional hp Finite Element Method algorithms (2D hp-FEM) with mixed triangular and rectangular finite elements. The two dimensional model is a starting point for the three dimensional model of self-adaptive hp-FEM presented in the second part of this paper. A computational mesh is represented by a composite graph. The operations performed over the mesh are expressed by the graph grammar rules. The three dimensional model is based on the extension of the two dimensional model with rectangular finite elements. In the second part …of this paper, we conclude the presentation with numerical examples concerning the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL). Show more

Keywords: Graph grammar, Automatic hp adaptivity, Finite Element Method

DOI: 10.3233/FI-2012-622

Citation: Fundamenta Informaticae, vol. 114, no. 2, pp. 149-182, 2012

Authors: Paszyńska, Anna | Grabska, Ewa | Paszyński, Maciej

Article Type: Research Article

Abstract: This paper presents a composite programmable graph grammar model of the three dimensional self-adaptive hp Finite Element Method (hp-FEM) algorithms. The computational mesh composed of hexahedral finite elements is represented by a composite graph. The operations performed over the mesh are expressed by composite graph grammar productions. The three dimensional model is based on the extension of the two dimensional model for rectangular finite elements. This paper is concluded with numerical examples, presenting the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL), the modern patterning process.

Keywords: Graph grammar, Automatic hp adaptivity, Finite Element Method, Step-and-Flash Imprint Lithography

DOI: 10.3233/FI-2012-623

Citation: Fundamenta Informaticae, vol. 114, no. 2, pp. 183-201, 2012

Authors: Yao, Chih-Chia | Lee, Kang

Article Type: Research Article

Abstract: The classification of texture images, especially those with spatial rotation and region shift, is a challenge and important problem in image analysis and classification. This paper proposes a novel algorithm design, an ellipse invariant algorithm, to improve the capability of texture classification for spatial rotation and region shift. The principle of an ellipse invariant algorithm is to use a minimum ellipse to enclose specific representative pixels extracted by the subtracting clustering method. After translating the coordinates, the ellipse in the rotated texture would be formulated as the ellipse in original texture. Also in this paper a hybrid texture filter is …proposed. In the hybrid texture filter the scheme of texture feature extraction include Gabor wavelet, neighboring grey level dependence matrix and the ellipse invariant algorithm. Support vector machines (SVMs) are introduced as the classifier. The proposed hybrid texture filter can classify both the stochastic textures and structural textures. Experimental results reveal that this proposed algorithm outperforms existing design algorithms. Show more

Keywords: texture, ellipse, rotation, shift

DOI: 10.3233/FI-2012-624

Citation: Fundamenta Informaticae, vol. 114, no. 2, pp. 203-220, 2012