Ամփոփում:

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 требуется найти такую линейную нумерацию его вершин, чтобы сумма длин ребер (абсолютное число разности номеров инцидентных ей вершин) была минимальна относительно всевозможных нумераций графа.

Հանձնման ամսաթիվը:

07.07.2016

Ընդունման ամսաթիվը:

26.10.2016

Նույնականացուցիչ:

oai:noad.sci.am:136061

ISSN:

0131-4645

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Mathematical Problems of Computer Science

Հատոր:

46

URL:

լրացուցիչ տեղեկատվություն:

david.h.muradian@gmail.com

Կազմակերպության անվանում:

Institute for Informatics and Automation Problems

Երկիր:

Armenia

Ինդեքսավորում:

ASCI