Source author record

Maxim A. Babenko

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics math.OC

Catalog footprint

Research overview

4works

4topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

A combinatorial algorithm for the planar multiflow problem with demands located on three holes

We consider an undirected multi(commodity)flow demand problem in which a supply graph is planar, each source-sink pair is located on one of three specified faces of the graph, and the capacities and demands are integer-valued and Eulerian. It is known that such a problem has a solution if the cut and (2,3)-metric conditions hold, and that the solvability implies the existence of an integer solution. We develop a purely combinatorial strongly polynomial solution algorithm.

preprint2012arXiv

On Weighted Multicommodity Flows in Directed Networks

Let $G = (VG, AG)$ be a directed graph with a set $S \subseteq VG$ of terminals and nonnegative integer arc capacities $c$ . A feasible multiflow is a nonnegative real function $F(P)$ of "flows" on paths $P$ connecting distinct terminals such that the sum of flows through each arc $a$ does not exceed $c(a)$ . Given $μ\colon S \times S \to \R_+$ , the \emph{ $μ$ -value} of $F$ is $\sum_P F(P) μ(s_P, t_P)$ , where $s_P$ and $t_P$ are the start and end vertices of a path $P$ , respectively. Using a sophisticated topological approach, Hirai and Koichi showed that the maximum $μ$ -value multiflow problem has an integer optimal solution when $μ$ is the distance generated by subtrees of a weighted directed tree and $(G,S,c)$ satisfies certain Eulerian conditions. We give a combinatorial proof of that result and devise a strongly polynomial combinatorial algorithm.

preprint2011arXiv

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

We consider an undirected graph $G = (VG, EG)$ with a set $T \subseteq VG$ of terminals, and with nonnegative integer capacities $c(v)$ and costs $a(v)$ of nodes $v\in VG$ . A path in $G$ is a \emph{ $T$ -path} if its ends are distinct terminals. By a \emph{multiflow} we mean a function $F$ assigning to each $T$ -path $P$ a nonnegative rational \emph{weight} $F(P)$ , and a multiflow is called \emph{feasible} if the sum of weights of $T$ -paths through each node $v$ does not exceed $c(v)$ . The \emph{value} of $F$ is the sum of weights $F(P)$ , and the \emph{cost} of $F$ is the sum of $F(P)$ times the cost of $P$ w.r.t. $a$ , over all $T$ -paths $P$ . Generalizing known results on edge-capacitated multiflows, we show that the problem of finding a minimum cost multiflow among the feasible multiflows of maximum possible value admits \emph{half-integer} optimal primal and dual solutions. Moreover, we devise a strongly polynomial algorithm for finding such optimal solutions.

preprint2010arXiv

A Faster Algorithm for the Maximum Even Factor Problem

Given a digraph $G = (VG,AG)$ , an \emph{even factor} $M \subseteq AG$ is a subset of arcs that decomposes into a collection of node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geleen and Cunningham and generalize path matchings in undirected graphs. Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard but for the class of \emph{odd-cycle symmetric} digraphs the problem is polynomially solvable. So far, the only combinatorial algorithm known for this task is due to Pap; it has the running time of $O(n^4)$ (hereinafter $n$ stands for the number of nodes in $G$ ). In this paper we present a novel \emph{sparse recovery} technique and devise an $O(n^3 \log n)$ -time algorithm for finding a maximum cardinality even factor in an odd-cycle symmetric digraph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.