# How much semigroup structure is needed to encode graphs ?

P. Goralčík; A. Goralčíková; V. Koubek

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1986)

- Volume: 20, Issue: 2, page 191-206
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topGoralčík, P., Goralčíková, A., and Koubek, V.. "How much semigroup structure is needed to encode graphs ?." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 20.2 (1986): 191-206. <http://eudml.org/doc/92256>.

@article{Goralčík1986,

author = {Goralčík, P., Goralčíková, A., Koubek, V.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {isomorphism complete; polynomial time isomorphism algorithm; critical varieties of finite semigroups},

language = {eng},

number = {2},

pages = {191-206},

publisher = {EDP-Sciences},

title = {How much semigroup structure is needed to encode graphs ?},

url = {http://eudml.org/doc/92256},

volume = {20},

year = {1986},

}

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

PB - EDP-Sciences

VL - 20

IS - 2

SP - 191

EP - 206

LA - eng

KW - isomorphism complete; polynomial time isomorphism algorithm; critical varieties of finite semigroups

UR - http://eudml.org/doc/92256

ER -

## References

top- 1. L. BABAI, Moderately exponential bound for graph isomorphism, FCT'81, Lecture Notes in Comp. Sci, n. 117, Springer, 1981, pp. 34-50. Zbl0462.68040MR652968
- 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. Zbl0381.68042MR483689
- 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. Zbl0178.01203
- 5. S. EILENBERG, Automata, Languages, and Machines, Vol. B, Academic Press, 1976. Zbl0359.94067MR530383
- 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. Zbl0476.68035MR652988
- 7. L. KUČERA and V. TRNKOVÁ, Isomorphism testing in unary algebras [to appear in SIAM J. Comput]. Zbl0665.68029MR953287
- 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.