Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Demel J., Demlová M., Koubek V. Theoretical Computer Science36 (2-3):203-216,1985.Type:Article
Date Reviewed: Jan 1 1986

This paper presents an interesting class of algorithms for finding the minimal nontrivial congruences, subalgebras, and ideals of a finite algebra specified by its table of operations. This algorithm is based on a clever modification of Tarjan’s algorithm for finding strongly corrected components of a graph [1]. The running times of the given algorithm are O(n1+r) for the case of congruences and O(nr) for subalgebras and ideals where n is the number of elements in the algebra and r is the maximum arity of its operations. Another interesting feature of the algorithm is that when the given algebra is, in fact, a group or ring, the complexity of finding minimal congruences reduces to O(n2).

Reviewer:  S. Lakshmivarahan Review #: CR109838
1) Tarjan, R. E.Depth-first-search and linear graph algorithms, SIAM J. Comput. 1 (1972), 146–160.
Bookmark and Share
  Featured Reviewer  
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Improving the performance guarantee for approximate graph coloring
Wigderson A. Journal of the ACM 30(4): 729-735, 1983. Type: Article
Feb 1 1985
Complexity of the word problem for commutative semigroups of fixed dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986
Calculation of Minkowski-reduced lattice bases
Afflerbach L., Grothe H. Computing 35(3-4): 269-276, 1985. Type: Article
Aug 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy