?
Faster algorithms for half-integral T -Path packing
P. 1–12.
Babenko M. A., 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.
In book
Vol. 92. , Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017.
Дистель Р., М.: МЦНМО, 2024.
С момента выхода первого издания на английском языке в 1997 году книга известного математика, профессора Гамбургского университета Рейнгарда Дистеля стала основным учебником по теории графов во многих университетах, выдержав к настоящему времени пять изданий, перевод последнего из которых предлагается читателю. Уникальность учебника в его глубине при относительно небольшом объёме: в книге найдутся задачи как доступные ...
Added: January 25, 2026
Beaudou L., Echeverría H., Foucaud F. et al., Procedia Computer Science 2025 Vol. 273 P. 86–93
We prove that the recognition of exact cubes of trees can be done in polynomial time. More precisely, the exact distance power of a graph is a refinement of the more usual notion of graph power. Given a graph G and a positive integer p, the exact distance pth power of G is the graph G#p on the same vertex set where two vertices ...
Added: December 3, 2025
Belova T., Dementiev Y., Fomin F. et al., , 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.
Added: October 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.
This article presents an overview of the main algorithms used in resource distribution problems. The description, input and output data, as well as peculiarities and complexity of these algorithms are considered. The paper proposes a modified algorithm for finding vapor combinations in a graph, which allows solving the problem of optimal load distribution between the ...
Added: December 25, 2023
Karpov A., Automation and Remote Control 2022 Vol. 83 P. 1329–1354
A survey of papers on practically significant restrictions on the preference profile of a collective is carried out, including single-peaked preferences, group-separable preferences, preferences with the single-crossing property, and Euclidean preferences and their extensions. Both ordinal and dichotomous preferences are considered. For structured preferences, we present characterization in terms of forbidden subprofiles and the probability ...
Added: October 31, 2022
А. В. Карпов, Автоматика и телемеханика 2022 № 9 С. 3–35
Проведен обзор работ по практически значимым ограничениям на профиль предпочтений коллектива: однопиковые предпочтения, сепарабельные предпочтения, предпочтения со свойством единственного пересечения, евклидовы предпочтения и их расширения. Рассмотрены как ординальные, так и дихотомические предпочтения. Для структурированных предпочтений представлена характеризация через запрещенные подпрофили и вероятность появления профиля с заданным свойством. Для сепарабельных предпочтений описан алгоритм построения иерархического дерева. ...
Added: September 15, 2022
Bychkov A., Pogudin G., 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 ...
Added: October 19, 2021
Springer, 2020.
This book constitutes the proceedings of the 15th International Computer Science Symposium in Russia, CSR 2020, held in Yekaterinburg, Russia, in June 2020.
The 25 full papers and 6 invited papers were carefully reviewed and selected from 49 submissions. The papers cover a broad range of topics, such as: algorithms and data structures; computational complexity, including ...
Added: September 4, 2020
Springer, 2019.
Added: August 4, 2019
Springer, 2018.
This book constitutes the refereed post-conference proceedings of the 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, held in Singapore, Singapore, in July 2018. The 31 regular papers presented in this volume were carefully reviewed and selected from 69 submissions. They cover diverse areas of combinatorical algorithms, complexity theory, graph theory and combinatorics, combinatorial optimization, ...
Added: October 23, 2018
Avdoshin S. M., Набебин А. А., М.: ДМК Пресс, 2019.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Sofya Kiselgof, Procedia Computer Science 2014 Vol. 31 P. 807–813
We investigate models of two-sided matching markets without transfers. Examples of such markets include marriage market, universities-applicants market and others. Gale and Shapley in 1962 first introduced this kind of problems in the literature. They considered one-to-one and one-to-many markets, where preferences of individuals on the one side over individuals on the other side were ...
Added: January 23, 2015
Sofya Kisel'gof, Automation and Remote Control 2014 Vol. 75 No. 6 P. 1069–1077
We consider an extension of the classical model of generalized Gale-Shapley matchings. The model describes a two-sided market: on one side, universities each of which has a restriction on the number of enrolled students; on the other side, applicants each of which can get a single place in the university. Both applicants and universities have ...
Added: October 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 ...
Added: October 23, 2014
Polyakov I. V., Chepovskiy A., Chepovskiy A., Вестник Новосибирского государственного университета. Серия: Информационные технологии 2013 Т. 11 № 4 С. 77–83
In this paper special data structure for big social graph storing and operating is presented. We discuss mainly graph paths searching, obtaining subgrapths and addition of new edges and vertices. ...
Added: October 17, 2013
Kiselgof S. G., , 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.
Matching problem with preferences being simplest semiorders is analysed. It is proved that a stable matching always exists. Furthermore, for any stable matching there exists a linear extension of preferences, which does not sontradict stability of a matching. In the college admission problem common goal is to find student-optimal stable matching. We provide a simple ...
Added: March 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.
The goal of the expert search task is nding knowledgeable persons within the enterprise. In this paper we focus on its distinctions from the other information retrieval tasks. We review the existing approaches and propose a new term weighting scheme which is based on analysis of communication patterns between people. The e ectiveness of the proposed ...
Added: March 20, 2013
Sofya Kiselgof, / Series "Matching in practice". 2012.
In this article we describe current university admission system in Ukraine. Current admission system in Ukraine is quazi-centralized. A matching mechanism consist of three stages, which are three stages of the classical deferred acceptance admission scheme. We also charachterize quota assignment process for state-financed and open-enrollment seats in Ukrainian universities. ...
Added: March 18, 2013
Péter Biró, Kiselgof S. G., / Series MT-DP "Discussion Papers of Hungarian Academy of Sciences". 2013. No. 6.
A common feature of the Hungarian, Irish, Spanish and Turkish higher education admission systems is that the students apply for programmes and they are ranked according to their scores. Students who apply for a programme with the same score are in a tie. Ties are broken by lottery in Ireland, by objective factors in Turkey ...
Added: March 11, 2013
Babenko M. A., Karzanov A. V., Journal of Combinatorial Optimization 2012 Vol. 24 No. 3 P. 202–228
We consider an undirected graph $G = (VG, EG)$ with a set $T \subseteq VG$ of terminals, and with nonnegative integer capacities $c(v)$ and costs $a(v)$ of nodes $v\in VG$. A path in $G$ is a \emph{$T$-path} if its ends are distinct terminals. By a \emph{multiflow} we mean a function $F$ assigning to each $T$-path ...
Added: January 27, 2013
Babenko M. A., Algorithmica 2012 Vol. 64 No. 3 P. 362–383
Given a digraph $G = (VG,AG)$, an even factor $M \subseteq AG$ is a set formed by node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geelen and Cunningham and generalize path matchings in undirected graphs. Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard ...
Added: January 27, 2013
Kiselgof S. G., Проблемы управления 2012 № 5 С. 33–40
In Russia from 2009 College admission is based on results of Unified State Exam. Entrant applies to no more than five universities. Admission mechanism is defined by government for all state universities. In the paper the authors model how entrant chooses university for application and, based on the entrant's choice prediction, the shortages of the ...
Added: November 17, 2012