?
Faster algorithms for half-integral T -Path packing
P. 1–12.
Бабенко М. А., Artamonov S.
Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m √n log n 2 /m log n ) -Time algorithm (hereinafter n := |V |, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2 , 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O ( m √n log n 2 /m log n )time, thus matching the complexities of integral and half-integral versions.
В книге
Vol. 92. , Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017.
Дистель Р., М.: МЦНМО, 2024.
С момента выхода первого издания на английском языке в 1997 году книга известного математика, профессора Гамбургского университета Рейнгарда Дистеля стала основным учебником по теории графов во многих университетах, выдержав к настоящему времени пять изданий, перевод последнего из которых предлагается читателю. Уникальность учебника в его глубине при относительно небольшом объёме: в книге найдутся задачи как доступные ...
Добавлено: 25 января 2026 г.
Beaudou L., Echeverría H., Foucaud F. и др., Procedia Computer Science 2025 Vol. 273 P. 86–93
Добавлено: 3 декабря 2025 г.
Belova T., Dementiev Y., Fomin F. и др., , in: 27th European Conference on Artificial Intelligence, 19–24 October 2024, Santiago de Compostela, Spain – Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024)Vol. 392.: IOS Press, 2024. P. 3461–3468.
Добавлено: 24 октября 2024 г.
Vladlena D. Markvirer, Ekaterina A. Karnaukhova, , in: 023 International Conference on Quality Management, Transport and Information Security, Information Technologies (IT&QM&IS).: Petrozavodsk: IEEE, 2023. P. 152–155.
Добавлено: 25 декабря 2023 г.
А. В. Карпов, Автоматика и телемеханика 2022 № 9 С. 3–35
Проведен обзор работ по практически значимым ограничениям на профиль предпочтений коллектива: однопиковые предпочтения, сепарабельные предпочтения, предпочтения со свойством единственного пересечения, евклидовы предпочтения и их расширения. Рассмотрены как ординальные, так и дихотомические предпочтения. Для структурированных предпочтений представлена характеризация через запрещенные подпрофили и вероятность появления профиля с заданным свойством. Для сепарабельных предпочтений описан алгоритм построения иерархического дерева. ...
Добавлено: 15 сентября 2022 г.
Бычков А., Погудин Г. А., ACM Communications in Computer Algebra 2021 Vol. 54 No. 3 P. 119–123
Transformation of a polynomial ODE system to a special quadratic form has been successfully used recently as a preprocessing step for model order reduction methods. However, to the best of our knowledge, there has been no practical algorithm for performing this step automatically with any optimality guarantees.
We present an algorithm that, given a system of ...
Добавлено: 19 октября 2021 г.
Springer, 2020.
Добавлено: 4 сентября 2020 г.
Springer, 2019.
Добавлено: 4 августа 2019 г.
Springer, 2018.
Добавлено: 23 октября 2018 г.
Авдошин С. М., Набебин А. А., М.: ДМК Пресс, 2019.
Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто ...
Добавлено: 24 августа 2018 г.
Sofya Kiselgof, Procedia Computer Science 2014 Vol. 31 P. 807–813
Добавлено: 23 января 2015 г.
Sofya Kisel'gof, Automation and Remote Control 2014 Vol. 75 No. 6 P. 1069–1077
Добавлено: 23 октября 2014 г.
Péter Biró, Sofya Kiselgof, Central European Journal of Operations Research 2015 Vol. 23 No. 4 P. 727–741
A common feature of the Hungarian, Irish, Spanish and Turkish higher education admission systems is that students apply for programmes and are ranked according to their scores. Students who apply for a programme with the same score are tied. Ties are broken by lottery in Ireland, by objective factors in Turkey (such as date of ...
Добавлено: 23 октября 2014 г.
Поляков И. В., Чеповский А. А., Чеповский А. М., Вестник Новосибирского государственного университета. Серия: Информационные технологии 2013 Т. 11 № 4 С. 77–83
В статье представлена специализированная структура данных, предназначенная для хранения и выполнения различных операций с графами социальных сетей больших объемов. Предложенная структура хранения ориентирована на поддержку операций пополнения и выгрузки подграфов и поиска кратчайших путей между двумя группами вершин. ...
Добавлено: 17 октября 2013 г.
Кисельгоф С. Г., , in: Game Theory and Management. Collected abstracts of papers presented on the Fifth International Conference Game Theory and Management.: St. Petersburg: Graduate School of Management, St. Petersburg University, 2011. P. 119–121.
Добавлено: 21 марта 2013 г.
Dmitry Romanov, Kravchenko A., , in: Concept Discovery in Unstructured Data. 2nd International Workshop, CDUD 2012, Leuven, Belgium, May 2012, ProceedingsIssue 871.: Leuven: Katholieke Universiteit Leuven, 2012. Ch. 5 P. 40–48.
Добавлено: 20 марта 2013 г.
Sofya Kiselgof, / Series "Matching in practice". 2012.
Добавлено: 18 марта 2013 г.
Péter Biró, Кисельгоф С. Г., / Series MT-DP "Discussion Papers of Hungarian Academy of Sciences". 2013. No. 6.
Добавлено: 11 марта 2013 г.
Бабенко М. А., Karzanov A. V., Journal of Combinatorial Optimization 2012 Vol. 24 No. 3 P. 202–228
Рассмотрим неориентированный граф $G = (VG, EG)$, в котором выделено множество терминалов $T \subseteq VG$, и заданы неотрицательные пропускные способности $c(v)$, а также стоимости $a(v)$ для всех вершин $v\in VG$. Путь в $G$ называется $T$-путем, если его концы представляют собой различные терминалы. Мультипотоком называется функция $F$, приписывающую каждому $T$-пути $P$ неотрицательный рациональный вес $F(P)$. Мультипоток ...
Добавлено: 27 января 2013 г.
Бабенко М. А., Algorithmica 2012 Vol. 64 No. 3 P. 362–383
Пусть задан орграф $G = (VG,AG)$. Четным фактором $M \subseteq AG$ называется множество ребер, образованное набором вершинно непересекающихся путей и четных циклов. Четные факторы были введены Гиленом и Каннингхемом, они обобщают т.н. path matchings в неориентированных графах. Задача нахождения четного фактора максимального размера в графе общего вида является NP-трудной, однако для класса нечетно циклически симметричных ...
Добавлено: 27 января 2013 г.
Кисельгоф С. Г., Проблемы управления 2012 № 5 С. 33–40
Приведены сведения о системе приема в вузы России на основании результатов Единого государственного экзамена (ЕГЭ). Построена математическая модель выбора абитуриентом вузов для подачи заявлений. На основе спрогнозированного выбора абитуриентов смоделирована приемная кампания. Показаны недостатки существующего механизма зачисления абитуриентов в вузы. ...
Добавлено: 17 ноября 2012 г.