Wyniki wyszukiwania - BazTech

1

Combinatorial Algorithms for Binary Operations on LR-tableaux with Entries Equal to 1 with Applications to Nilpotent Linear Operators

Kaniecki Mariusz, Kosakowska Justyna

Fundamenta Informaticae

|

2020

|

Vol. 174, nr 2

121--136

EN

In the paper we investigate an algorithmic associative binary operation * on the set ℒℛ1 of Littlewood-Richardson tableaux with entries equal to one. We extend * to an algorithmic nonassociative binary operation on the set ℒℛ1 × ℕ and show that it is equivalent to the operation of taking the generic extensions of objects in the category of homomorphisms from semisimple nilpotent linear operators to nilpotent linear operators. Thus we get a combinatorial algorithm computing generic extensions in this category.

2

Graph Theoretical and Algorithmic Characterizations of Positive Definite Symmetric Quasi-Cartan Matrices

Abarca M., Rivera D.

Fundamenta Informaticae

|

2016

|

Vol. 149, nr 3

241--261

EN

A well known constructive proof for the ADE-classification of many mathematical objects, such as positive unit forms and their associated quasi-Cartan matrices, has lead to an Inflations Algorithm. However, this algorithm is not known to run in polynomial time. In this paper we use a so called flation transformation and show how its invariants can be used to characterize the Dynkin types A and D in the language of graph theory. Also, a polynomial-time algorithm for computing the Dynkin type is suggested.

3

An Algorithmic-type Classification of Tetravalent One-regular Graphs Using Computer Algebra Tools

Ghasemi M.

Fundamenta Informaticae

|

2014

|

Vol. 135, nr 3

211--228

EN

A finite graph is one-regular if its automorphism group acts regularly on the set of its arcs. In the present paper, tetravalent one-regular graphs of order 7p2., where p is a prime, are classified using computer algebra tools.

4

Inflation Algorithms for Positive and Principal Edge-bipartite Graphs and Unit Quadratic Forms

Kosakowska J.

Fundamenta Informaticae

|

2012

|

Vol. 119, nr 2

149-162

EN

We describe combinatorial algorithms that compute the Dynkin type (resp. Euclidean type) of any positive (resp. principal) unit quadratic form q : Z^n →Z and of any positive (resp. principal) edge-bipartite connected graph Δ. The study of the problem is inspired by applications of the algorithms in the representation theory, in solving a class of Diophantine equations, in the study of mesh geometries of roots, in the spectral analysis of graphs, and in the Coxeter-Gram classification of edge-bipartite graphs.

5

Internet shopping optimization problem

Błażewicz J., Kovalyov M. Y., Musiał J., Urbański A. P., Wojciechowski A.

International Journal of Applied Mathematics and Computer Science

|

2010

|

Vol. 20, no 2

385-390

EN

A high number of Internet shops makes it difficult for a customer to review manually all the available offers and select optimal outlets for shopping. A partial solution to the problem is brought by price comparators which produce price rankings from collected offers. However, their possibilities are limited to a comparison of offers for a single product requested by the customer. The issue we investigate in this paper is a multiple-item multiple-shop optimization problem, in which total expenses of a customer to buy a given set of items should be minimized over all available offers. In this paper, the Internet Shopping Optimization Problem (ISOP) is defined in a formal way and a proof of its strong NP-hardness is provided. We also describe polynomial time algorithms for special cases of the problem.