16 Result(s)
within
Alexander V. Karzanov
-
Article
Higher Bruhat orders of types B and C
We propose versions of higher Bruhat orders for types B and C. This is based on a theory of higher Bruhat orders of type A and their geometric interpretations (due to Manin–Shekhtman, Voevodskii–Kapranov, and Zie...
-
Article
On interrelations between strongly, weakly and chord separated set-systems (a geometric approach)
We consider three types of set-systems that have interesting applications in algebraic combinatorics and representation theory: maximal collections of the so-called strongly, weakly, and chord separated subsets o...
-
Chapter and Conference Paper
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 ar...
-
Article
Planar flows and quadratic relations over semirings
Adapting Lindström’s well-known construction, we consider a wide class of functions which are generated by flows in a planar acyclic directed graph whose vertices (or edges) take weights in an arbitrary commut...
-
Article
Min-cost multiflows in node-capacitated undirected networks
We consider an undirected graph G=(VG,EG) with a set T⊆VG of terminals, and with nonnegative integer capacities c(v) and costs a(v) of nodes v∈VG. A path in G is a T-path if its ends are distinct terminals. By a
-
Article
On maximal weakly separated set-systems
For a permutation ω∈S n , Leclerc and Zelevinsky in Am. Math. Soc. Transl., Ser. 2 181, 85–108 (1998) introduced the concept of an ω-chamber weakly separ...
-
Chapter and Conference Paper
A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem
We study the problem of finding a fractional node-capacitated multiflow of maximum value in an undirected network. Previously known methods for this problem are based on linear programming and the ellipsoid me...
-
Article
Maximum skew-symmetric flows and matchings
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate flows in antisymmetrical digra...
-
Chapter and Conference Paper
Integer Concave Cocirculations and Honeycombs
A convex triangular grid is a planar digraph G embedded in the plane so that each bounded face is an equilateral triangle with three edges and their union
-
Article
Metrics with finite sets of primitive extensions
In this paper, we give a complete characterization for the class of rational finite metrics μ with the property that the set Π(μ) of primitive extensions of μ is finite. Here, for a metric μ on a setT, a positive...
-
Article
A Combinatorial Algorithm for the Minimum (2, r)-Metric Problem and Some Generalizations
be a graph with nonnegative integer capacities c(e) of the edges , and let μ be a metric that establishes distances on the pairs of elements of a subset ...
-
Article
A Fast Algorithm For Finding A Maximum Free Multiflow In An Inner Eulerian Network And Some Generalizations
be a network, where is an undirected graph with nodes and edges, ...
-
Article
Multiflows and disjoint paths of minimum total cost
In this paper we discuss a number of recent and earlier results in the field of combinatorial optimization that concerns problems on minimum cost multiflows (multicommodity flows) and edge-disjoint paths. More...
-
Article
Path problems in skew-symmetric graphs
We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for ...
-
Chapter and Conference Paper
Maximum skew-symmetric flows
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 the newly de...
-
Article
Cyclical games with prohibitions
We consider a certain combinatorial game on a digraph for two cases of the price function. For one case the game in question extends the cyclical game studied in Ehrenfeucht and Mycielski (1979) and Gurvitch, ...
