Maxim A. Babenko

collaborators

4 papers

math.CO2006

Optimum Branching Problem Revisited

Maxim A. Babenko, Pavel V. Nalivaiko

Given a digraph $G = (V_{G}, A_{G})$ , a \emph{branching} in $G$ is a set of arcs $B \subseteq A_{G}$ such that the underlying undirected graph spanned by $B$ is acyclic and each node in…

math.CO2006

On a Problem Posed by Maurice Nivat

Maxim A. Babenko

Consider a $m \times n$ matrix $A$ , whose elements are arbitrary integers. Consider, for each square window of size $2 \times 2$ , the sum of the corresponding elements of $A$ . Thes…

math.CO2006

On Ear Decompositions of Strongly Connected Bidirected Graphs

Maxim A. Babenko

Bidirected graphs (earlier studied by Edmonds, Johnson and, in equivalent terms of skew-symmetric graphs, by Tutte, Goldberg, Karzanov, and others) proved to be a useful unifying l…

math.CO2006

Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs

Maxim A. Babenko, Alexander V. Karzanov

The problem of finding, in an edge-weighted bidirected graph $G = (V, E)$ , a cycle with minimum mean weight of its edges generalizes similar problems for both directed and undirected…