We continue the study of boundary classes for NP-hard problems and focus on seven NP-
hard graph problems involving non-local properties: Hamiltonian Cycle, Hamiltonian Cycle …

Matrix representations are a powerful tool for designing efficient algorithms for combinatorial
optimization problems such as matching, and linear matroid intersection and parity. In this …

In this paper, we consider the computation of the degree of the Dieudonné determinant of a
linear symbolic matrix A=A_0+A_1x_1+⋯+A_mx_m, where each A_i is an n*n polynomial …

We give better approximation ratios for two Steiner Tree variants by combining known
algorithms: the optimum 3-decomposition and iterative randomized rounding. The first …

Abstract Let f: 2 N→ Z+ be a polymatroid (an integer-valued non-decreasing submodular set
function with f (∅)= 0). A k-polymatroid satisfies that f (e)≤ k for all e∈ N. We call S⊆ N …

We address the 1-line Steiner tree problem with minimum number of Steiner points. Given a
line l, a point set P of n terminals in R 2 and a positive constant K, we are asked to find a …

We address the computation of the degrees of minors of a noncommutative symbolic matrix
of form A [c]:=∑ k= 1 m A ktckxk, where A k are matrices over a field K, xk are …

We show new algorithms and constructions over linear delta-matroids. We observe an
alternative representation for linear delta-matroids, as a contraction representation over a …

The weighted T-free 2-matching problem is the following problem: given an undirected
graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum …

In this paper, we address computation of the degree deg Det A of Dieudonné determinant
Det A of A=∑ k= 1 m A kxktck, where A k are n× n matrices over a field K, xk are …