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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.