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. 
@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. L. Babai, Moderately exponential bound for graph isomorphism, FCT'81, Lecture Notes in Comp. Sci, n. 117, Springer, 1981, pp. 34-50. | MR | Zbl

2. K. S. Booth, Isomorphism testing for graphs, semigroups, and finite automata are polynomially equivalent problems, SIAM J. Comput. Vol. 7, 1976, pp. 273-279. | MR | Zbl

3. K. S. Booth and Ch. J. Colbourn, Problems polynomially equivalent to graph isomorphism, Tech. Rep. CS-77-04, Univ. of Waterloo, 1979.

4. A. H. Clifford and G. B. Preston, The algebraic theory of semigroups, A.M.S., Providence, Rhode Island, 1967. | Zbl

5. S. Eilenberg, Automata, Languages, and Machines, Vol. B, Academic Press, 1976. | MR | Zbl

6. L. Kučera and V. Trnková, Isomorphism completeness for some algebraic structures, FCT'81, Lecture Notes in Comp. Sci, n. 117, Springer, 1981, pp. 218-225. | MR | Zbl

7. L. Kučera and V. Trnková, Isomorphism testing in unary algebras [to appear in SIAM J. Comput]. | MR | Zbl

8. S. Micali and V. V. Vazirani, An O(√|v|.|E|) algorithm for finding maximum matching in generai graphs, Proc. FOCS'80, pp. 17-27.