Advanced Search

Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function: $L₅\left(D\right)=ma{x}_{1\le i\le p}(ma{x}_{e\in S_i\cap D}w\left(e\right)-mi{n}_{e\in S_i\cap D}w\left(e\right))$ For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary...

Suppose a graph $G=(V,E)$ whose edges are partitioned into $p$ disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number $p$ of categories and present some polynomial algorithm.

A matrix $A$ is said to have $𝐗$-simple image eigenspace if any eigenvector $x$ belonging to the interval $𝐗=\{x:\underline{x}\le x\le \overline{x}\}$ containing a constant vector is the unique solution of the system $A\otimes y=x$ in $𝐗$. The main result of this paper is an extension of $𝐗$-simplicity to interval max-min matrix $𝐀=\{A:\underline{A}\le A\le \overline{A}\}$ distinguishing two possibilities, that at least one matrix or all matrices from a given interval have $𝐗$-simple image eigenspace. $𝐗$-simplicity of interval matrices in max-min algebra are studied and equivalent conditions for interval...

We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.