A polynomial recognition of unit forms using graph-based strategies
| Autor: | Diane Castongay, Thomas Brüstle, Jesmmer Alves |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Exponential complexity
Weakly positive Applied Mathematics Graph based Breadth-first search 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Polynomial algorithm Representation theory Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Algebraic expression Time complexity Mathematics |
| Zdroj: | Discrete Applied Mathematics. 253:61-72 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2018.06.018 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect