How much semigroup structure is needed to encode graphs ?
Goralčík, P. ; Goralčíková, A. ; Koubek, V.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 20 (1986), p. 191-206 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1986-01-01
@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},
     volume = {20},
     year = {1986},
     pages = {191-206},
     mrnumber = {860769},
     zbl = {0601.20053},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 191-206. http://gdmltest.u-ga.fr/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.