5 papers
Upper Bound for Permanent Saturation of Metric Graphs using Interval Exchange Transformations
Egor Ermolaev, Vsevolod Chernyshev, Alexandra Skripchenko
We study upper bounds for the moment of permanent -saturation in finite metric graphs. The dynamics is generated by moving points travelling with unit speed along edge…
DFS-based fast crack pre-detection
Duc Nguyen, Vsevolod Chernyshev, Vitalii Makogin +1
This paper develops a computationally efficient pre-detection method for cracks in three-dimensional CT images of concrete. Instead of attempting full voxel-wise crack segmentation…
A Faster Algorithm for Independent Cut
Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach +1
The previously fastest algorithm for deciding the existence of an independent cut had a runtime of , where is the order of the input graph. We improve…
The Canadian Traveller Problem on outerplanar graphs
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev +5
We study the -Canadian Traveller Problem, where a weighted graph with a source and a target are given. This problem also has a hidden input $E_* \…
Forest Cuts in Sparse Graphs
Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach
We propose the conjecture that every graph of order with less than edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts a…