Journal or Publication Title:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Date of publication:

2016

Volume:

46

ISSN:

0131-4645

Additional Information:

Մուրադյան Դ., Мурадян Д.

Title:

A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs

Other title:

Պոլինոմիալ բարդությամբ ալգորիթմ ինտերվալ գրաֆների բարձրությունը գտնելու համար; Алгоритм полиномиальной сложности для нахождения высоты графов интервалов

Creator:

David H. Muradian

Subject:

Mathematics ; Science ; Graph theory ; Algorithm

Uncontrolled Keywords:

Graph layout ; Bandwidth ; Interval Graphs

Coverage:

73-80

Abstract:

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.

Publisher:

Изд-во НАН РА

Date created:

2016-11-17

Type:

Հոդված

Format:

pdf

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան