5 papers · 1 filter
Constrained Shortest Path and Hierarchical Structures
Adil Erzin, Roman Plotnikov, Ilya Ladygin
The Constraint Shortest Path (CSP) problem is as follows. An -vertex graph is given, each edge/arc assigned two weights. Let us call them "cost" and "length" for definiteness. F…
A 3/2--approximation for big two-bar charts packing
Adil Erzin, Stepan Nazarenko, Gregory Melidi +1
We consider a Two-Bar Charts Packing Problem (2-BCPP), in which it is necessary to pack two-bar charts (2-BCs) in a unit-height strip of minimum length. The problem is a generaliza…
Two-Bar Charts Packing Problem
Adil Erzin, Gregory Melidi, Stepan Nazarenko +1
We consider a Bar Charts Packing Problem (BCPP), in which it is necessary to pack bar charts (BCs) in a strip of minimum length. The problem is, on the one hand, a generalization o…
Constructive Heuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem
Roman Plotnikov, Adil Erzin
We consider a Min-Power Bounded-Hops Symmetric Connectivity problem that consists in the construction of communication spanning tree on a given graph, where the total energy consum…
FPTAS for barrier covering problem with equal circles in 2D
Adil Erzin, Natalya Lagutkina
In this paper, we consider a problem of covering a straight line segment by equal circles that are initially arbitrarily placed on a plane by moving their centers on a segment or o…