Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2020

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Efficient Computation of the Large Inductive Dimension Using Order- and Graph-theoretic Means

Berghammer Rudolf, Schnoor Henning, Winter Michael

Fundamenta Informaticae

2020

Vol. 177, nr 2

95--113

Finite topological spaces and their dimensions have many applications in computer science, e.g., in digital topology, computer graphics and the analysis and synthesis of digital images. Georgiou et. al. [11] provided a polynomial algorithm for computing the covering dimension dim (X, 𝒯 ) of a finite topological space (X, 𝒯 ). In addition, they asked whether algorithms of the same complexity for computing the small inductive dimension ind (X, 𝒯 ) and the large inductive dimension Ind (X, 𝒯 ) can be developed. The first problem was solved in a previous paper [4]. Using results of the that paper, we also solve the second problem in this paper. We present a polynomial algorithm for Ind (X, 𝒯 ), so that there are now efficient algorithms for the three most important notions of a dimension in topology. Our solution reduces the computation of Ind (X, 𝒯 ), where the specialisation pre-order of (X, 𝒯 ) is taken as input, to the computation of the maximal height of a specific class of directed binary trees within the partially ordered set. For the latter an efficient algorithm is presented that is based on order- and graph-theoretic ideas. Also refinements and variants of the algorithm are discussed.