Wyniki wyszukiwania - Biblioteka Nauki

1

On the key exchange with new cubical maps based on graphs

100%

Romańczuk U. , Ustimenko V.

|

tom Vol. 11, no. 4

11--19

EN

Families of edge transitive algebraic graphs Fn(K), over the commutative ring K were used for the graph based cryptographic algorithms. We introduce a key exchange protocol defined in terms of bipartite graph An(K), n ≥ 2 with point set Pn and line set Ln isomorphic to n-dimensional free module Kn. Graphs A(n, K) are not vertex and edge transitive. There is a well defined projective limit lim A(n, K) = A(K), n → ∞ which is an infinite bipatrtite graph with point set P = lim Pn and line set L = limLn. Let K be a commutative ring contain at least 3 regular elements (not zero divisors). For each pair of (n, d), n ≥ 2, n ≥ 1 and sequence of elements α1, α2, …, α2d, such that α1, αi+αi+1, i = 1, 2, …, 2d, i = 1, 2, … 2d-1 and α2d+α1 are regular elements of the ring K. We define polynomial automorphism hn = hn (d, α1, α2, …, α2d) of variety Ln (or Pn). The existence of projective limit lim An(K) guarantees the existence of projective limit h = h(d, α1, α2, …, α2d) = lim hn, n → ∞ which is cubical automorphism of infinite dimensional varieties L (or P). We state that the order of h is an infinity. There is a constant n0 such that hn, n ≥ n0 is a cubical map. Obviously the order of hn is growing with the growth of n and the degree of polynomial map (hn)k from the Cremona group of all polynomial automorphisms of free module Kn with operation of composition is bounded by 3. Let τ be affine automorphism of Kn i.e. the element of Cremona group of degree 1. We suggest symbolic Diffie Hellman key exchange with the use of cyclic subgroup of Cremona group generated by τ-1hnτ. In the case of K = Fp, p is prime, the order of hn is the power of p. So the order is growing with the growth of p. We use computer simulation to evaluate the orders in some cases of K = Zm, where m is a composite integer.

2

3-biplacement of bipartite graphs

100%

Adamus L. , Leśniak E. , Orchel B.

|

2008

|

tom Vol. 28, no. 3

223-231

EN

Let G = (L,R;E) be a bipartite graph with color classes L and R and edge set E. A set of two bijections {φ1, φ2}, φ1, φ2 : L ∪ R → L ∪ R, is said to be a 3-biplacement of G if [formula], where φ*/1, φ*/2 are the maps defined on E, induced by φ1, φ2, respectively. We prove that if ‌L‌ = p, ‌R‌ = q, 3 ≤ p ≤ q, then every graph G = (L, R; E) of size at most p has a 3-biplacement.

3

Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments

100%

Duraj S. , Kopeć P. , Kubale M. , Pikies T.

|

tom Vol. 11, no. 1-2

53--61

EN

In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.

4

Endomorphism monoid of diamond product of two common complete bipartite graphs

100%

Jiarasuksakun T. , Rutjanisarakul T. , Thongjua W.

|

tom Vol. 15

59--66

EN

An endomorphism of a graph G = (V, E) is a mapping f : V → V such that for all x, y ∈ V if {x, y} ∈ E, then {f (x),f (y)}∈ E. Let End(G) be the class of all endomorphisms of graph G. The diamond product of graph G = (V, E) (denoted by G ◊ G) is a graph defined by the vertex set V (G ◊ G) = End(G) and the edge set E (G ◊ G) ={{f, g} ⊂ End(G)|{f(x), g(x)} ∈ E for all x ∈ V}. Let Km,n be a complete bipartite graph on m + n vertices. This research aims to study the algebraic property of V (Km,n ◊ Km,n) = End(Km,n) after we have found that Km,n ◊ Km,n is also a complete bipartite graph on mmnn + nmmn vertices. The result shows that all of its vertices (endomorphisms) form a noncommutative monoid.

5

Minimal fixed point sets of relative maps

88%

Zhao X. Z.

|

tom 162

|

nr 2

163-180

EN

Let f: (X,A) → (X,A) be a self map of a pair of compact polyhedra. It is known that f has at least N(f;X,A) fixed points on X. We give a sufficient and necessary condition for a finite set P (|P| = N(f;X,A)) to be the fixed point set of a map in the relative homotopy class of the given map f. As an application, a new lower bound for the number of fixed points of f on Cl(X-A) is given.

6

On the General Position Number of Complementary Prisms

88%

Neethu P. K. , Chandran S. V. U. , Changat M. , Klavžar S.

|

tom Vol. 178, nr 3

267--281

EN

The general position number gp(G ) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism G G ¯ of G is the graph formed from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. It is proved that gp(G G ¯ ) ≤ n (G ) + 1 if G is connected and gp(G G ¯ ) ≤ n (G ) if G is disconnected. Graphs G for which gp(G G ¯ ) = n (G ) + 1 holds, provided that both G and G ¯ are connected, are characterized. A sharp lower bound on gp(G G ¯ ) is proved. If G is a connected bipartite graph or a split graph then gp(G G ¯ ) ∈ {n (G ), n (G )+1}. Connected bipartite graphs and block graphs for which gp(G G ¯ ) = n (G ) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.

7

A Bipartite Graph for Estimating Measurement Uncertainty on Five-Axis Machining Centres

88%

Stryczek R.

|

tom Vol. 18, no 6

449--464

EN

The essential source of errors in machining on five-axis milling centres are errors caused by the improper calibration of a machine tool, setup errors and a process plan which is not designed optimally. For the multilateral machining of the complex, precise parts of machines, a process plan should include, before and during the process, coordinate measurements by means of a touch probe in order to verify previously made surfaces or to determine accurately the position and orientation of a local coordinate system. The uncertainty of these measurements is connected with the estimate precision of performing the manufactured parts. This paper presents a tool devised for determining the uncertainty of the results of coordinate measurements by a simulation method, which is also useful at the stage of machine tool calibration. A basis of this method is a bipartite graph with a tree structure. Transitions in the graph constitute a set of elementary measurement activities and analytical activities which determine the uncertainty of the position and orientation of respective geometric features and abstract objects. Based on the results of the conducted simulation tests it is possible to build analytical models for the rapid determination of measurement uncertainty. The tool devised is aimed at vector dimensioning and therefore it enables simple extension, including integration with geometric dimensioning and tolerancing. This paper includes an example of applying the method devised, which confirms its practicability.

8

Model przydziału zasobów do zadań w przedsiębiorstwie transportowym

75%

Izdebski M. , Jacyna M.

|

tom nr 4

PL

W artykule zdefiniowano ogólny problem przydziału, wyjaśniono pojęcie skojarzenia w grafie dwudzielnym a następnie opisano problem przydziału w przedsiębiorstwie transportowym. Wyznaczono model matematyczny przydziału, funkcję optymalizacyjną.

EN

This article defines a general assignment problem and explains definition of a matching in a bipartite graph. This paper describes an assignment problem of tasks to resources in the transport company. This article contains the mathematical allocation model of tasks, function optimization with constrains.