@article{ITA_1986__20_2_191_0, author = {Goral\v{c}{\'\i}k, P. and Goral\v{c}{\'\i}kov\'a, A. and Koubek, V.}, title = {How much semigroup structure is needed to encode graphs ?}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {191--206}, publisher = {AFCET - Gauthier-Villars}, address = {Paris}, volume = {20}, number = {2}, year = {1986}, mrnumber = {860769}, zbl = {0601.20053}, language = {en}, url = {http://www.numdam.org/item/ITA_1986__20_2_191_0/} }
TY - JOUR AU - Goralčík, P. AU - Goralčíková, A. AU - Koubek, V. TI - How much semigroup structure is needed to encode graphs ? JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1986 SP - 191 EP - 206 VL - 20 IS - 2 PB - AFCET - Gauthier-Villars PP - Paris UR - http://www.numdam.org/item/ITA_1986__20_2_191_0/ LA - en ID - ITA_1986__20_2_191_0 ER -
%0 Journal Article %A Goralčík, P. %A Goralčíková, A. %A Koubek, V. %T How much semigroup structure is needed to encode graphs ? %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1986 %P 191-206 %V 20 %N 2 %I AFCET - Gauthier-Villars %C Paris %U http://www.numdam.org/item/ITA_1986__20_2_191_0/ %G en %F ITA_1986__20_2_191_0
Goralčík, P.; Goralčíková, A.; Koubek, V. How much semigroup structure is needed to encode graphs ?. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 20 (1986) no. 2, pp. 191-206. http://www.numdam.org/item/ITA_1986__20_2_191_0/
1. Moderately exponential bound for graph isomorphism, FCT'81, Lecture Notes in Comp. Sci, n. 117, Springer, 1981, pp. 34-50. | MR | Zbl
,2. Isomorphism testing for graphs, semigroups, and finite automata are polynomially equivalent problems, SIAM J. Comput. Vol. 7, 1976, pp. 273-279. | MR | Zbl
,3. Problems polynomially equivalent to graph isomorphism, Tech. Rep. CS-77-04, Univ. of Waterloo, 1979.
and ,4. The algebraic theory of semigroups, A.M.S., Providence, Rhode Island, 1967. | Zbl
and ,5. Automata, Languages, and Machines, Vol. B, Academic Press, 1976. | MR | Zbl
,6. Isomorphism completeness for some algebraic structures, FCT'81, Lecture Notes in Comp. Sci, n. 117, Springer, 1981, pp. 218-225. | MR | Zbl
and ,7. Isomorphism testing in unary algebras [to appear in SIAM J. Comput]. | MR | Zbl
and ,8. An O(√|v|.|E|) algorithm for finding maximum matching in generai graphs, Proc. FOCS'80, pp. 17-27.
and ,