On enumeration of tree-rooted planar cubic maps

Y. Kochetkov

?

On enumeration of tree-rooted planar cubic maps

2016. No. 1608.02510.

We consider planar cubic maps, i.e. connected cubic graphs, embedded into plane, with marked spanning tree and marked directed edge (not in this tree). The number of such objects with 2n vertices is C2n∙ Cn+1, where Ck is Catalan number.

Language: English

Full text

Keywords: spanning tree остовное дерево Planar cubic map плоская кубическая карта

Win-win алгоритм для задачи (k+1)-LST/k-путевого представления

Ключиков А. Г., Vyalyi M., Дискретный анализ и исследование операций 2021 Т. 28 № 4 С. 117–124

We describe a win-win algorithm that produces in polynomial of size of a graph G and given parameter k time either a spanning tree with al least k + 1 leaves or a path decomposition with width at most k. This algorithm is optimal due to the path decomposition theorem. ...

Added: February 2, 2022

Fast protocols for leader election and spanning tree construction in a distributed network

M.N.Vyalyi, Khuziev I. M., Problems of Information Transmission 2017 Vol. 53 No. 2 P. 183–201

We consider leader election and spanning tree construction problems in a synchronous network. Protocols are designed under the assumption that nodes in the network have identifiers but the size of an identifier is unlimited. We present fast protocols with runtime O(Dlog L+L), where L is the size of the minimal identifier and D is the network diameter. ...

Added: October 16, 2017

On enumeration of tree-rooted planar cubic maps. II

Kochetkov Y., / Series arXiv "math". 2017. No. 1703.04390.

In work [4] tree-rooted planar cubic maps with marked directed edge (not in this tree) were enumerated. The number of such objects with 2n vertices is C2n ∙ Cn+1, where Ck is Catalan number. In this work a marked directed edge is not demanded, i.e. we enumerate tree-rooted planar cubic maps. Formulas are more complex, ...

Added: March 14, 2017

Распределенная коммуникационная сложность построения остовного дерева

Vyalyi M., Хузиев И. М., Проблемы передачи информации 2015 Т. 51 № 1 С. 54–71

We consider the problem of constructing a spanning tree in a synchronized network with an unknown topology. We give lower and upper bounds on the complexity of protocols for spanning tree constriction in various settings: for deterministic and probabilistic protocols, networks with distinguishable nodes, and anonymous networks. We present suboptimal protocols for which the multiplicative gap from the lower ...

Added: July 10, 2015

Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs

Gurvich V., Vyalyi M., Discrete Applied Mathematics 2012 Vol. 160 P. 1742–1756

Added: October 18, 2014