Abstract:

Let G be a connected graph with vertex set X and edge set U. A layout of G is a one-to-one map φ from X onto {1, 2, . . . , |X|}. The bandwidth of φ is �� φ (��) = max φ (��) − φ (��), where (u, v) ranges over all edges of G. The bandwidth of G, denoted by B(G), is defined as B(G) = min�� φ (��) where φ ranges over all layouts of G. Interval graphs are the intersection graphs of a family of intervals over the real line. In this paper we show that the Bandwidth Minimization problem for interval graphs can be solved in time O(nΔ2log(Δ)), where n is the vertex number and Δ is the maximal degree of vertex of the interval graph.
; Пусть G=(X, U) – граф со множеством вершин X и ребер U. Каждое взаимно-однозначное отображение φ:X→{1,2….|X|} назовем его нумерацией. При этом число | φ (��)− φ (��)| назовем длиной ребра (x,y), а числа Bφ (G)=max(��,��)∈U| φ (��)− φ (��)| и B(G)=min B φ (G), где минимум берется по всевозможным нумерациям графа G, соответственно - высотой нумерации φ и графа G. Граф интервалов определяется как граф пересечений семейства интервалов данных на числовой прямой. В настоящей работе приводится алгоритм полиномиальной сложности для нахождения высоты произвольного графа интервалов. Алгоритм имеет сложность O(nΔ2log(Δ)), где n – количество вершин, а Δ – максимальная степень вершин графа.

Date accepted:

21.07.2016

Date issued:

24.10.2016

Identifier:

oai:noad.sci.am:136066

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