Abstract:

The minimal linear arrangement problem (MinLA) is defined as follows: given a graph G, find a linear ordering (layout) φφ for the vertices of G on a line such that the sum of the edge lengths is minimized over all orderings. Edge length for an edge (x, y) is defined as φφ(����)−φφ(����). In this paper we describe the class of minimal orderings of the special case of tridimensional grids – Cartesian product of three simple paths, when one of them consists of two vertices.
; В работе описывается класс минимальных по длине нумераций частного случая трехмерных решеток – декартого произведения трех простых цепей, когда один из них состоит из двух вершин. Минимальная длина нумерациия графа определяется следующим образом: для данного графа G требуется найти такую линейную нумерацию его вершин, чтобы сумма длин ребер (абсолютное число разности номеров инцидентных ей вершин) была минимальна относительно всевозможных нумераций графа.

Date submitted:

07.07.2016

Date accepted:

26.10.2016

Identifier:

oai:noad.sci.am:136061

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

46

URL:

Additional Information:

david.h.muradian@gmail.com

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

ASCI