RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Алгебра и анализ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Алгебра и анализ, 2003, том 15, выпуск 6, страницы 1–34 (Mi aa823)  

Эта публикация цитируется в 23 научных статьях (всего в 23 статьях)

Статьи

Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время

С. А. Евдокимовa, И. Н. Пономаренкоb

a Санкт-Петербургский институт информатики и автоматизации РАН
b С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия

Аннотация: Построен алгоритм полиномиальной сложности для распознавания и нахождения канонической пометки произвольных циркулянтных графов, который включает в себя нахождение циклической базы произвольной разрешимой группы перестановок. Корректность алгоритма опирается на новый результат о структуре колец Шура над конечной циклической группой.

Полный текст: PDF файл (1908 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
St. Petersburg Mathematical Journal, 2004, 15:6, 813–835

Реферативные базы данных:

Поступила в редакцию: 15.05.2003

Образец цитирования: С. А. Евдокимов, И. Н. Пономаренко, “Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время”, Алгебра и анализ, 15:6 (2003), 1–34; St. Petersburg Math. J., 15:6 (2004), 813–835

Цитирование в формате AMSBIB
\RBibitem{EvdPon03}
\by С.~А.~Евдокимов, И.~Н.~Пономаренко
\paper Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время
\jour Алгебра и анализ
\yr 2003
\vol 15
\issue 6
\pages 1--34
\mathnet{http://mi.mathnet.ru/aa823}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2044629}
\zmath{https://zbmath.org/?q=an:1061.05045}
\transl
\jour St. Petersburg Math. J.
\yr 2004
\vol 15
\issue 6
\pages 813--835
\crossref{https://doi.org/10.1090/S1061-0022-04-00833-7}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/aa823
  • http://mi.mathnet.ru/rus/aa/v15/i6/p1

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. И. Н. Пономаренко, “Нахождение группы автоморфизмов циркулянтной ассоциативной схемы за полиномиальное время”, Вопросы теории представлений алгебр и групп. 12, Зап. научн. сем. ПОМИ, 321, ПОМИ, СПб., 2005, 251–267  mathnet  mathscinet  zmath; I. N. Ponomarenko, “Finding the automorphism group of a circulant association scheme in polynomial time”, J. Math. Sci. (N. Y.), 136:3 (2006), 3972–3979  crossref
    2. Junttila T., Kaski P., “Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs”, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics, SIAM Proceedings Series, 2007, 135–149  isi
    3. Evdokimov, S, “Permutation group approach to association schemes”, European Journal of Combinatorics, 30:6 (2009), 1456  crossref  mathscinet  zmath  isi  scopus
    4. Muzychuk, M, “Schur rings”, European Journal of Combinatorics, 30:6 (2009), 1526  crossref  mathscinet  zmath  isi  scopus
    5. Penso L.D., Rautenbach D., Szwarcfiter J.L., “Long cycles and paths in distance graphs”, Discrete Mathematics, 310:23 (2010), 3417–3420  crossref  mathscinet  zmath  isi  scopus
    6. Araujo J., Dobson E., Konieczny J., “Automorphisms of endomorphism semigroups of reflexive digraphs”, Mathematische Nachrichten, 283:7 (2010), 939–964  mathscinet  zmath  isi
    7. Evdokimov S., Ponomarenko I., “Schur rings over a Galois ring of odd characteristic”, Journal of Combinatorial Theory Series A, 117:7 (2010), 827–841  crossref  mathscinet  zmath  isi  scopus
    8. Penso L.D., Rautenbach D., Szwarcfiter J.L., “Cycles, Paths, Connectivity and Diameter in Distance Graphs”, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, 5911, 2010, 320–328  crossref  mathscinet  zmath  isi  scopus
    9. Э. А. Монахова, “Структурные и коммуникативные свойства циркулянтных сетей”, ПДМ, 2011, № 3(13), 92–115  mathnet
    10. Loewenstein Ch., Rautenbach D., Regen F., “On Hamiltonian paths in distance graphs”, Appl Math Lett, 24:7 (2011), 1075–1079  crossref  mathscinet  zmath  isi  scopus
    11. Lin M.Ch., Rautenbach D., Soulignac F.J., Szwarcfiter J.L., “Powers of cycles, powers of paths, and distance graphs”, Discrete Appl Math, 159:7 (2011), 621–627  crossref  mathscinet  zmath  isi  scopus
    12. Nicoloso S., Pietropaoli U., “Isomorphism testing for circulant graphs C-n(a, b)”, Util Math, 87 (2012), 165–182  mathscinet  zmath  isi
    13. С. А. Евдокимов, И. Н. Пономаренко, “Шуровость $\mathrm S$-колец над циклической группой и обобщенное сплетение групп перестановок”, Алгебра и анализ, 24:3 (2012), 84–127  mathnet  mathscinet  zmath  elib; S. A. Evdokimov, I. N. Ponomarenko, “Schurity of $\mathrm S$-rings over a cyclic group and generalized wreath product of permutation groups”, St. Petersburg Math. J., 24:3 (2013), 431–460  crossref  isi  elib
    14. I. N. Ponomarenko, “Bases of schurian antisymmetric coherent configurations and isomorphism test for schurian tournaments”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. научн. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 108–147  mathnet  mathscinet; J. Math. Sci. (N. Y.), 192:3 (2013), 316–338  crossref
    15. Loewenstein Ch., Rautenbach D., Sotak R., “On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs”, Discret. Math. Theor. Comput. Sci., 16:1 (2014), 7–30  mathscinet  zmath  isi
    16. Muzychuk M., “a Solution of An Equivalence Problem For Semisimple Cyclic Codes”, Topics in Finite Fields, Contemporary Mathematics, 632, eds. Kyureghyan G., Mullen G., Pott A., Amer Mathematical Soc, 2015, 327–334  crossref  mathscinet  zmath  isi
    17. Evdokimov S., Ponomarenko I., “Coset Closure of a Circulant S-Ring and Schurity Problem”, J. Algebra. Appl., 15:4 (2016), 1650068  crossref  mathscinet  zmath  isi  elib  scopus
    18. S. Evdokimov, I. Ponomarenko, “On the separability problem for circulant S-rings”, Алгебра и анализ, 28:1 (2016), 32–51  mathnet  mathscinet  elib; St. Petersburg Math. J., 28:1 (2017), 21–35  crossref  isi
    19. S. Evdokimov, M. Muzychuk, I. Ponomarenko, “A family of permutation groups with exponentially many nonconjugated regular elementary Abelian subgroups”, Алгебра и анализ, 29:4 (2017), 45–52  mathnet  mathscinet  elib; St. Petersburg Math. J., 29:4 (2018), 575–580  crossref  isi
    20. I. Ponomarenko, A. Vasil'ev, “Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time”, Вопросы теории представлений алгебр и групп. 31, Зап. научн. сем. ПОМИ, 455, ПОМИ, СПб., 2017, 154–180  mathnet
    21. Fiala J., Klavik P., Kratochvil J., Nedela R., “3-Connected Reduction For Regular Graph Covers”, Eur. J. Comb., 73 (2018), 170–210  crossref  mathscinet  zmath  isi  scopus
    22. Muzychuk M., Ponomarenko I., “Finding a Cycle Base of a Permutation Group in Polynomial Time”, J. Algebra, 510 (2018), 542–561  crossref  mathscinet  zmath  isi  scopus
    23. Г. К. Рябов, “Об отделимости колец Шура над абелевыми $p$-группами”, Алгебра и логика, 57:1 (2018), 73–101  mathnet  crossref; G. K. Ryabov, “Separability of Schur rings over Abelian $p$-groups”, Algebra and Logic, 57:1 (2018), 49–68  crossref  isi
  • Алгебра и анализ St. Petersburg Mathematical Journal
    Просмотров:
    Эта страница:383
    Полный текст:153
    Литература:35
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020