M. Babenko

activity

20052014

most citedOn Weighted Multicommodity Flows in Directed Networks

3 citations · 4 across the 8 of their papers we have counts for

collaborators

Showing 2010Show all

4 papers · 1 filter

math.CO2010★ 1 cited

Triangle-Free 2-Matchings Revisited

Maxim Babenko, Alexey Gusakov, Ilya Razenshteyn

A \emph{2-matching} in an undirected graph $G = (V G, E G)$ is a function $f : E G \to {0, 1, 2}$ such that for each node $v \in V G$ the sum of values $f (e)$ on all edges $e$ i…

math.CO2010

A Faster Algorithm for the Maximum Even Factor Problem

Maxim A. Babenko

Given a digraph $G = (V G, A G)$ , an \emph{even factor} $M \subseteq A G$ is a subset of arcs that decomposes into a collection of node-disjoint paths and even cycles. Even factors in…

math.CO2010

A Linear Time Algorithm for Finding Three Edge-Disjoint Paths in Eulerian Networks

Maxim Babenko, Ignat Kolesnichenko, Ilya Razenshteyn

Consider an undirected graph $G = (V G, E G)$ and a set of six \emph{terminals} $T = {s_{1}, s_{2}, s_{3}, t_{1}, t_{2}, t_{3}} \subseteq V G$ . The goal is to find a collection $\calP$ of thr…

math.CO2010

On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks

Maxim A. Babenko, Alexander V. Karzanov

We consider an undirected graph $G = (V G, E G)$ with a set $T \subseteq V G$ of terminals, and with nonnegative integer capacities $c (v)$ and costs $a (v)$ of nodes $v \in V G$ . A path…