Name
Abstract | ||
|---|---|---|
The units forms are algebraic expressions that have important role in representation theory of algebras. We identified that existing algorithms have exponential time complexity for weakly nonnegative and weakly positive types. In this paper we introduce a polynomial algorithm for the recognition of weakly nonnegative unit forms. The related algorithm identifies hypercritical restrictions in a given unit form, testing every subgraph of 9 vertices of the unit form associated graph. By adding Depth First Search approach, a similar strategy could be used in the recognition of weakly positive unit forms. We also present the most popular methods to decide whether or not a unit form is weakly nonnegative or weakly positive, we analyze their time complexity and we compare the results with our algorithms. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.dam.2018.06.018 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Integral quadratic form,Unit form,Critical unit form,Hypercritical unit form,Polynomial algorithm,Graph | Discrete mathematics,Graph,Combinatorics,Polynomial,Vertex (geometry),Breadth-first search,Representation theory,Exponential complexity,Algebraic expression,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
253 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jesmmer Alves | 1 | 0 | 0.34 |
| Diane Castongay | 2 | 0 | 0.34 |
| Thomas Brüstle | 3 | 0 | 0.68 |