Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: edge-bipartite graphs

Sortuj według:

Ogranicz wyniki do:

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

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.

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

Kosakowska J.

Fundamenta Informaticae

2012

Vol. 119, nr 2

149-162

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.