• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 15 публикаций
Сортировка:
по названию
по году
Статья
Babenko M. A., Artamonov S. European Journal of Combinatorics. 2018. P. 3-23.

A perfect 2-matching in an undirected graph G=(V,E) is a function x:E→0,1,2 such that for each node v∈V the sum of values x(e) on all edges e incident to v equals 2. If supp(x)=e∈E∣x(e)≠0 contains no triangles then x is called triangle-free. Polyhedrally speaking, triangle-free 2-matchings are harder than 2-matchings, but easier than usual 1-matchings. Given edge costs c:E→R + , a natural combinatorial problem consists in finding a perfect triangle-free matching of minimum total cost. For this problem, Cornuéjols and Pulleyblank devised a combinatorial strongly-polynomial algorithm, which can be implemented to run in O(VElogV) time. (Here we write V, E to indicate their cardinalities |V|, |E|.) If edge costs are integers in range [0,C] then for both 1- and 2-matchings some faster scaling algorithms are known that find optimal solutions within O(Vα(E,V)logVElog(VC)) and O(VElog(VC)) time, respectively, where α denotes the inverse Ackermann function. So far, no efficient cost-scaling algorithm is known for finding a minimum-cost perfect triangle-free2-matching. The present paper fills this gap by presenting such an algorithm with time complexity of O(VElogVlog(VC)).

Добавлено: 1 марта 2018
Статья
Feigin B. L., Jimbo M., Kashiwara M. et al. European Journal of Combinatorics. 2004. Vol. 25. No. 8. P. 1197-1229.
Добавлено: 28 мая 2010
Статья
Magazinov A. European Journal of Combinatorics. 2013. Vol. 34. No. 7. P. 1108-1113.
Добавлено: 4 октября 2018
Статья
Kiselev S., Balogh J., Cherkashin D. European Journal of Combinatorics. 2019. Vol. 79C. P. 228-236.
Добавлено: 22 апреля 2019
Статья
Burman Y. M., Zvonkine D. European Journal of Combinatorics. 2010. Vol. 31. No. 1. P. 129-144.

Каждому представлению цикла длины n (в группе Sn) в виде произведения транспозций мы ставим в соответствие моном от переменных wij, который хранит информацию о транспозициях, но не об их порядке. Суммируя полученные мономы по всем представлениям, мы получаем многочлен, для которого находим явное выражение. Из этого выражения выводится формула для количества  одногранных вложений заданного графа.

Добавлено: 7 ноября 2012
Статья
Omelchenko A., Краско Е. С. European Journal of Combinatorics. 2017. Vol. 62. P. 167-177.
Добавлено: 29 августа 2018
Статья
Shabanov D. A. European Journal of Combinatorics. 2015. Vol. 43. P. 185-203.
Добавлено: 6 октября 2015
Статья
Lozin V. V., Mayhil C., Zamaraev V. A. European Journal of Combinatorics. 2012. Vol. 33. No. 4. P. 534-543.

Для класса графов X, через Xn обозначается количество графов с множеством вершин {1, . . . , n} из класса X. Класс X называется факториальным, если X – наследственный (т.е. замкнут относительно изоморфизма и операции удаления вершины) и nc1n ≤ Xn ≤ nc2n для некоторых положительных констант c1 и c2. Наследственные классы с субфакториальными функциями числа n-вершинных графов хорошо изучены. Ситуация с факториальными классами существенно сложнее и менее изучена. Хорошо изучены только классы, для которых функция числа n-вершинных растет не быстрее, чем числа Белла. Для того, чтобы лучше понять структуру факториальных классов, мы вводим понятие локально ограниченных покрытий и показываем, что различные классы графов могут быть описаны с помощью этого понятия.

Добавлено: 28 июня 2012
Статья
Shitov Y. European Journal of Combinatorics. 2015. Vol. 44. No. A. P. 140-143.
Добавлено: 30 октября 2014
Статья
Kulakova E., Lando S., Mukhutdinova T. et al. European Journal of Combinatorics. 2014. Vol. 41. P. 266-277.
Добавлено: 26 октября 2014
Статья
Bufetov A. I., Klimenko A. V. European Journal of Combinatorics. 2012. Vol. 33. No. 7. P. 1427-1443.

We give a brief survey of the method of Markov operators in the study of ergodic theorems for actions of free groups.

Добавлено: 3 декабря 2012
Статья
Dutour Sikirić M., Grishukhin V., Magazinov A. European Journal of Combinatorics. 2014. Vol. 42. P. 49-73.
Добавлено: 4 октября 2018
Статья
Shabanov D. A., Krokhmal N. E., Kravtsov D. A. European Journal of Combinatorics. 2019. Vol. 78. P. 28-43.
Добавлено: 4 февраля 2019
Статья
Shitov Y. European Journal of Combinatorics. 2014. Vol. 42. P. 107-111.
Добавлено: 23 июня 2014
Статья
Feigin E. European Journal of Combinatorics. 2012. Vol. 33. No. 1. P. 1913-1918.

Недавно было показано, что нормализованные числа Дженокки второго рода равны эйлеровым характеристикам вырожденных многообразий флагов. Q-аналоги чисел Дженокки естественным образом определяются как полиномы Пуанкаре выцрожденных многообразий флагов. Мы доказываем, что производящая функция полиномов Пуанкаре даётся простой непрерывной дробью. В качестве приложения, мы доказываем, что полиномы Пуанкаре совпадают с q-версией нормализованных чисел Дженокки второго рода, введённых Ханом и Зенгом.

Добавлено: 18 июля 2012