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…
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…
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…
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…
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_* \s…