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\'aclav},
     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},
     zbl = {0601.20053},
     mrnumber = {860769},
     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áclav
TI  - How much semigroup structure is needed to encode graphs ?
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1986
DA  - 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/
UR  - https://zbmath.org/?q=an%3A0601.20053
UR  - https://www.ams.org/mathscinet-getitem?mr=860769
LA  - en
ID  - ITA_1986__20_2_191_0
ER  - 
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 652968 | Zbl 0462.68040

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 483689 | Zbl 0381.68042

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 0178.01203

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

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 652988 | Zbl 0476.68035

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

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.