Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Faster algorithms for packing forests in graphs and related problems
Pavel Arkhipov, Vladimir Kolmogorov
We consider several problems related to packing forests in graphs. The first one is to find edge-disjoint forests in a directed graph of maximal size such that the indegree…
cs.DS2024
Bounded indegree -forests problem and a faster algorithm for directed graph augmentation
Pavel Arkhipov, Vladimir Kolmogorov
We consider two problems for a directed graph , which we show to be closely related. The first one is to find edge-disjoint forests in of maximal size such that the inde…
math.CO2024
Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results
Pavel Arkhipov
This paper focuses on Majority Dynamics in sparse graphs, in particular, as a tool to study internal cuts. It is known that, in Majority Dynamics on a finite graph, each vertex eve…