Metadata language
Title:
Linear Orderings of Tridimensional Grids ; Линейные нумерации трехмерных решеток
Author:
Muradian David ; Мурадян Давид
Type:
Uncontrolled Keywords:
Linear ordering ; Minimal Linear Arrangement Problem ; Grids ; Wirelength
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:
Date accepted:
ISSN:
Language:
Journal or Publication Title:
Mathematical Problems of Computer Science
Volume:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems