On maximal weakly separated set-systems (2009)
Danilov, Vladimir I., Karzanov, Alexander V., Koshevoy, Gleb A.
For a permutation $\omega\in S_n$, Leclerc and Zelevinsky \cite{LZ} introduced a concept of $\omega$-{\em chamber weakly separated collection} of subsets of $\{1,2,...,n\}$ and conjectured that all...
Pl\"ucker environments, wiring and tiling diagrams, and weakly separated set-systems (2009)
Danilov, Vladimir I., Karzanov, Alexander V., Koshevoy, Gleb A.
For the ordered set $[n]$ of $n$ elements, we consider the class $\Bscr_n$ of bases $B$ of tropical Pl\"ucker functions on $2^{[n]}$ such that $B$ can be obtained by a series of mutations (flips)...
On bases of tropical Pl\"ucker functions (2007)
Danilov, Vladimir I., Karzanov, Alexander V., Koshevoy, Gleb A.
We consider functions $f:B\to\Rset$ that obey tropical analogs of classical Pl\"ucker relations on minors of a matrix. The most general set $B$ that we deal with in this paper is of the form $\{x\in...
Andrew V. Goldberg, Alexander V. Karzanov
Abstract. We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest paths problems. We develop duality theory for the skew-symmetric...
Minimum Mean Cycle Problem in Bidirected and Skew-Symmetric Graphs (2006)
Babenko, Maxim A., Karzanov, Alexander V.
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 graphs. (The...
Integer concave cocirculations and honeycombs (2004)
A convex triangular grid is represented by a planar digraph $G$ embedded in the plane so that (a) each bounded face is surrounded by three edges and forms an equilateral triangle, and (b) the union...
Maximum Skew-Symmetric Flows and Matchings (2004)
Andrew V. Goldberg, Alexander V. Karzanov
The maximum integer skew-symmetric ow problem (MSFP) generalizes both the maximum ow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate ows in antisymmetrical...
Concave cocirculations in a triangular grid (2003)
Let $G=(V(G),E(G))$ be a planar digraph embedded in the plane in which all inner faces are equilateral triangles (with three edges in each), and let the union $\Rscr$ of these faces forms a convex...
Maximum Skew-Symmetric Flows and Matchings (2003)
Goldberg, Andrew V., Karzanov, Alexander V.
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte in terms of self-conjugate flows in antisymmetrical...
How to Uncross Some Modular Metrics (2000)
Let $\mu$ be a metric on a set T, and let c be a nonnegative function on the unordered pairs of elements of a superset $V\supseteq T$. We consider the problem of minimizing the inner product $c\cdot...
Maximum Skew-Symmetric Flows and Their Applications to B-Matchings (1999)
Andrew V. Goldberg, Alexander V. Karzanov
We introduce the maximum integer skew-symmetric flow problem (MSFP) which generalizes both the maximum flow and maximum matching problems. We establish analogs of the classical flow decomposition,...
Alexander V. Karzanov, S. Thomas McCormick
We consider the problem of minimizing a separable convex objective function over the linear space given by a system Mx = 0 with M a totally unimodular matrix. In particular, this generalizes the...
On Integer Multiflow Maximization (1997)
Andras Frank, Alexander V. Karzanov, Andras Sebö
Generalizing the two-commodity flow theorem of Rothschild and Whinston and the multiflow theorem of Lov'asz and Cherkasskij, Karzanov and Lomonosov proved a min-max theorem on maximum multiflows...
Maximum Skew-Symmetric Flows (1995)
Andrew V. Goldberg, Alexander V. Karzanov
We introduce the maximum skew-symmetric flow problem which generalizes flow and matching problems. We develop a theory of skew-symmetric flows that is parallel to the classical flow theory. We use...
Transitive Fork Environments And Minimum Cost Multiflows (1993)
Andrew V. Goldberg, Alexander V. Karzanov
. The following minimum cost maximum multiflow problem is the focus of the paper: () given an undirected graph G = (V G; EG), a subset T 2 V G (of terminals), and functions c : EG ! ZZ + (of...