Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 46, 73--80, 2016. A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs David H. Muradian Institute for Informatics and Automation Problems of NAS RA e-mail: david.h.muradian@gmail.com 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. Keywords: Graph layout, Bandwidth, Interval Graphs. 1. Introduction The bandwidth minimization problem for graphs was first stated in 1966 by Harper ([1]), where the problem was solved for hypercubes. Finding the bandwidth of an arbitrary graph is an NP-complete problem ([2]) and it remains NP-complete for many simple structures, e.g., for cyclic caterpillars with hair length 1, graphs in which the removal of all pendant vertices results in a simple cycle ([3]). There are only few classes of graphs for which an efficient solution (i.e., a polynomial algorithm or analytic result) to the bandwidth problem is known. Classes of graphs the bandwidth of which can be computed efficiently are butterflies ([4]), chain graphs ([5]), caterpillars with hair length at most 2 ([6]). Another nontrivial class, for which the problem was solved efficiently, is the class of interval graphs, graphs which are the intersection graphs of a family of intervals over the real line. The first polynomial algorithm for interval graphs was given in 1986 by the author ([7]). It was published in the Reports of NAS RA, where the algorithm is described in detail, and besides a brief proof of its correctness is given. Since this result was obtained independently and published in the following years ([8], [9], [10]), we consider it reasonable to publish the full proof of our algorithm’s correctness. 73 A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs 74 2. Preliminaries Let 𝐺𝐺 be a connected graph with vertex set 𝑋𝑋 and edge set 𝑈𝑈. A numbering of 𝐺𝐺 is a one-to-one map 𝜑𝜑 from 𝑋𝑋 onto {1, 2, . . . , | 𝑋𝑋|}. The bandwidth of 𝜑𝜑 is 𝐵𝐵𝜑𝜑(𝐺𝐺)= max | 𝜑𝜑(𝑢𝑢) − 𝜑𝜑(𝑣𝑣)|, where (𝑢𝑢, 𝑣𝑣) ranges over all edges of 𝐺𝐺. The bandwidth of 𝐺𝐺, denoted by 𝐵𝐵(𝐺𝐺), is defined as 𝐵𝐵(𝐺𝐺) = min 𝐵𝐵𝜑𝜑(𝐺𝐺), where 𝜑𝜑 ranges over all numberings of 𝐺𝐺. Length of an edge (𝑢𝑢, 𝑣𝑣) is defined as | 𝜑𝜑(𝑢𝑢) − 𝜑𝜑(𝑣𝑣)|. Given a graph 𝐺𝐺(𝑋𝑋, 𝑈𝑈) and its some layout 𝜑𝜑. Let’s define a new layout 𝜑𝜑𝐴𝐴,𝐵𝐵 – swap of two disjoint subsets 𝐴𝐴 and 𝐵𝐵 of 𝑋𝑋 as follows. If 𝐴𝐴 and 𝐵𝐵 are disjoint subsets of vertices of 𝐺𝐺, at that for any 𝑥𝑥 ∈ 𝐴𝐴 and 𝑦𝑦 ∈ 𝐵𝐵 we have 𝜑𝜑(𝑥𝑥) < 𝜑𝜑(𝑦𝑦) and max 𝑧𝑧∈𝐵𝐵 𝜑𝜑(𝑧𝑧) − min 𝑧𝑧∈𝐴𝐴 𝜑𝜑(𝑧𝑧) = |𝐴𝐴| + |𝐵𝐵| − 1, then 𝜑𝜑(𝑧𝑧)/ 𝑧𝑧 ∈ 𝑋𝑋\(𝐴𝐴 ∪ 𝐵𝐵) 𝜑𝜑𝐴𝐴,𝐵𝐵(𝑧𝑧) = 𝜑𝜑(𝑧𝑧) + |𝐵𝐵|/𝑧𝑧 ∈ 𝐴𝐴 𝜑𝜑(𝑧𝑧) − |𝐴𝐴|/𝑧𝑧 ∈ 𝐵𝐵 Let’s denote 𝑋𝑋𝜑𝜑[𝑘𝑘, 𝑙𝑙] = {𝑥𝑥 ∈ 𝑋𝑋/𝑘𝑘 ≤ 𝜑𝜑(𝑥𝑥) ≤ 𝑙𝑙} for 1 ≤ k ≤ l ≤ n. Let’s consider an interval graph 𝐺𝐺 = (𝑋𝑋, 𝑈𝑈). Let’s denote by 𝑥𝑥� an interval corresponding to the vertex 𝑥𝑥 ∈ 𝑋𝑋. We say that an interval 𝑥𝑥� = (𝑎𝑎, 𝑏𝑏) is entirely on the left side (right side) of an interval 𝑦𝑦� = (𝑐𝑐, 𝑑𝑑) if 𝑏𝑏 < 𝑐𝑐 (correspondingly 𝑎𝑎. 𝑑𝑑. Let’s denote by 𝛤𝛤−(𝑥𝑥�) (𝛤𝛤+(𝑥𝑥�)) the set of intervals which entirely are on the left side (correspondingly - on the right side) of 𝑥𝑥�. Let’s define a layout 𝜑𝜑0 for the graph 𝐺𝐺. For any vertices 𝑥𝑥, 𝑦𝑦 ∈ 𝑋𝑋 if 𝛤𝛤−(𝑥𝑥�) = 𝛤𝛤−(𝑦𝑦�) and 𝛤𝛤+(𝑥𝑥�) = 𝛤𝛤+(𝑦𝑦�), then 𝜑𝜑0(𝑥𝑥) < 𝜑𝜑0(𝑦𝑦) or 𝜑𝜑0(𝑥𝑥) > 𝜑𝜑0(𝑦𝑦). Otherwise, 𝜑𝜑0(𝑥𝑥) < 𝜑𝜑0(𝑦𝑦) if and only if 𝛤𝛤−(𝑥𝑥�) ⊂ 𝛤𝛤−(𝑦𝑦�) or 𝛤𝛤−(𝑥𝑥�) = 𝛤𝛤−(𝑦𝑦�) but 𝛤𝛤+(𝑥𝑥�) ⊂ 𝛤𝛤+(𝑦𝑦�). It is easy to check that 𝜑𝜑0 is well-defined by the above conditions and has the following properties. 1. If 𝑥𝑥� is entirely on the left side of 𝑦𝑦�, then 𝜑𝜑0(𝑥𝑥) < 𝜑𝜑0(𝑦𝑦). It is obvious by the definition. 2. If 1 ≤ i < j ≤ n and the vertices 𝑥𝑥 = 𝜑𝜑0−1(𝑖𝑖), 𝑦𝑦 = 𝜑𝜑0−1(𝑗𝑗) are adjacent, then 𝑥𝑥 is adjacent to any vertex 𝑧𝑧 = 𝜑𝜑0−1(𝑘𝑘), where i < k ≤ j. Really, let’s assume that 𝑥𝑥, 𝑧𝑧 are not adjacent. Then 𝑥𝑥� is entirely on the left side of �̂�𝑧. The vertices 𝑧𝑧, 𝑦𝑦 should be adjacent, otherwise as 𝑥𝑥, 𝑦𝑦 are adjacent, then 𝑦𝑦� should be entirely on the left side of �̂�𝑧 and therefore should have a smaller number in the layout 𝜑𝜑0. If 𝑧𝑧, 𝑦𝑦 are adjacent, then again 𝑦𝑦� should have a smaller number than �̂�𝑧 because 𝛤𝛤−(𝑦𝑦�) ⊂ 𝛤𝛤−(�̂�𝑧) (at least on account of 𝑥𝑥�), which leads to a contradiction. 3. Let x and y be vertices for which we have 𝛤𝛤−(𝑦𝑦�) ⊂ 𝛤𝛤−(𝑥𝑥�) and 𝛤𝛤+(𝑦𝑦�) ⊂ 𝛤𝛤+(𝑥𝑥�). Then two disjoint intervals exist, one of which is entirely on the left side and the other – entirely on the right side of 𝑥𝑥� and both are overlaps with 𝑦𝑦�. It is obvious by definition. Let 𝑥𝑥�, 𝑦𝑦�, 𝑧𝑧1� and 𝑧𝑧2� be intervals where 𝑧𝑧1� is entirely on the left side of 𝑥𝑥� and 𝑧𝑧2� - entirely on the right side of 𝑥𝑥� and all of them overlap with 𝑦𝑦�. Then we will say that 𝑥𝑥� is a proper interval for 𝑦𝑦� and record this fact as 𝑥𝑥 ⊂̇ 𝑦𝑦. For any vertex 𝑥𝑥 ∈ 𝑋𝑋, we will name 𝜑𝜑0(𝑥𝑥) as its index. D. Muradian 75 3. Algorithm Step i (i ≥ 1). At step i the algorithm having as an input the layout 𝜑𝜑 = 𝜑𝜑𝑖𝑖−1, creates a layout 𝜑𝜑𝑖𝑖 or stops, claiming that 𝐵𝐵(𝐺𝐺) > 𝐾𝐾. Let 𝑦𝑦 be a vertex with the greatest number at 𝜑𝜑, which is incident to an edge with a length above 𝐾𝐾, and let (𝑥𝑥, 𝑦𝑦) have the greatest length among them (i.e., 𝑦𝑦 is not adjacent to vertices, the numbers of which are less than 𝜑𝜑(𝑥𝑥)). Then the algorithm tries to find a vertex with the smallest number from 𝑋𝑋𝜑𝜑[𝜑𝜑(𝑥𝑥) + 1, 𝜑𝜑(𝑦𝑦) − 1], which is not adjacent to y. If such vertex does not exist, then it claims that 𝐵𝐵(𝐺𝐺) > 𝐾𝐾. Let 𝑧𝑧 be the sought-for vertex. Let’s denote 𝑀𝑀 = 𝑋𝑋𝜑𝜑[𝜑𝜑(𝑥𝑥), 𝜑𝜑(𝑧𝑧) − 1]. Let 𝑎𝑎𝑗𝑗 be a vertex from the set 𝑀𝑀\𝑋𝑋𝜑𝜑�𝜑𝜑�𝑎𝑎𝑗𝑗−1�, 𝜑𝜑(𝑧𝑧) − 1� having the greatest index there (with an agreement, that 𝑋𝑋𝜑𝜑[𝜑𝜑(𝑎𝑎0), 𝜑𝜑(𝑧𝑧) − 1] = ∅). Denote 𝑆𝑆𝑗𝑗 = 𝑋𝑋𝜑𝜑�𝜑𝜑�𝑎𝑎𝑗𝑗� + 1, 𝜑𝜑�𝑎𝑎𝑗𝑗−1� − 1�. Note that for some j-s sets 𝑆𝑆𝑗𝑗 may be empty. The layout 𝜑𝜑𝑖𝑖 is defined as follows: 𝜑𝜑𝑖𝑖−1(𝑥𝑥)/ 𝑎𝑎 = 𝑧𝑧 𝜑𝜑𝑖𝑖(𝑎𝑎) = 𝜑𝜑𝑖𝑖−1(𝑎𝑎)/𝑎𝑎 ∈ ⋃ 𝑆𝑆𝑗𝑗 ∪ �𝑋𝑋\(𝑀𝑀 ∪ {𝑧𝑧})�𝑗𝑗 𝜑𝜑𝑖𝑖−1(𝑎𝑎) + 1 + �𝑆𝑆𝑗𝑗�/𝑎𝑎 = 𝑎𝑎𝑗𝑗 In other words 𝜑𝜑𝑖𝑖 is obtained from 𝜑𝜑𝑖𝑖−1 via successive swaps: (M,{𝑧𝑧}), ({𝑎𝑎1}, 𝑆𝑆1), ({𝑎𝑎2}, 𝑆𝑆2), … Then the algorithm checks if there is an edge with the length above 𝐾𝐾 at 𝜑𝜑𝑖𝑖. If not, then it stops, claiming that 𝜑𝜑𝑖𝑖 is the sought-for layout with the bandwidth no more than 𝐾𝐾. If yes, then the algorithm turns to the step 𝑖𝑖 + 1. 4. Proof of the Algorithm’s Correctness Let’s define a class of layouts Φ0 for the graph 𝐺𝐺: 𝜑𝜑 ∈ Φ0 if and only if for any vertices a and b, for which 𝜑𝜑(𝑎𝑎) < 𝜑𝜑(𝑏𝑏) and 𝜑𝜑0(𝑎𝑎) > 𝜑𝜑0(𝑏𝑏), will take place 𝑎𝑎 ⊂̇ 𝑏𝑏. From the definition of Φ0 it follows immediately that for any 𝜑𝜑 ∈ Φ0 and two non- adjacent vertices x and y, if 𝜑𝜑0(𝑥𝑥) < 𝜑𝜑0(𝑦𝑦), then 𝜑𝜑(𝑥𝑥) < 𝜑𝜑(𝑦𝑦). It is easy to see that 𝜑𝜑0 ∈ Φ0. Moreover, the algorithm, beginning with 𝜑𝜑0, never leaves the class Φ0. Lemma 1: 𝜑𝜑𝑖𝑖 ∈ Φ0 in each step 𝑖𝑖. Proof: We will prove the statement by induction. For 𝑖𝑖 = 0 the statement obviously is true, let it be true for each step until 𝑖𝑖 − 1. Let’s show that 𝜑𝜑𝑖𝑖 ∈ Φ0. Then it is sufficient to show that 𝑧𝑧 ⊂̇ 𝑞𝑞 any 𝑞𝑞 ∈ 𝑀𝑀, and 𝑎𝑎𝑡𝑡 ⊂̇ 𝑞𝑞𝑡𝑡 for all 𝑞𝑞𝑡𝑡 ∈ 𝑆𝑆𝑡𝑡. Since (𝑞𝑞, 𝑦𝑦) ∈ 𝑈𝑈 and (𝑧𝑧, 𝑦𝑦) ∉ 𝑈𝑈, then naturally q cannot be a proper interval for z, and by the fact that 𝜑𝜑𝑖𝑖−1 ∈ Φ0, we will have 𝜑𝜑0(𝑞𝑞) < 𝜑𝜑0(𝑧𝑧). But as 𝛤𝛤+(𝑞𝑞�) ⊂ 𝛤𝛤+(�̂�𝑧), it follows immediately that 𝛤𝛤−(𝑞𝑞�) ⊂ 𝛤𝛤−(�̂�𝑧), 𝑖𝑖.e., 𝑧𝑧 ⊂̇ 𝑞𝑞. Then the layout obtained by the swap of M and {z} certainly belongs to Φ0, and therefore, 𝑎𝑎𝑡𝑡 ⊂̇ 𝑞𝑞𝑡𝑡 for all 𝑞𝑞𝑡𝑡 ∈ 𝑆𝑆𝑡𝑡. This proves the lemma. In the next two lemmas several new properties of the layout 𝜑𝜑𝑖𝑖 are proved. Lemma 2: In the step 𝑖𝑖, the length of the edge (𝑥𝑥, 𝑦𝑦) decreases by 1 and none of vertices from 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑦𝑦) + 1, 𝑛𝑛] is incident to an edge with the length above K. Proof: By Lemma 1 we have 𝑧𝑧 ⊂̇ 𝑥𝑥, and z together with x don’t have adjacent vertices in 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑦𝑦) + 1, 𝑛𝑛]. Therefore, there is no vertex from 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑦𝑦) + 1, 𝑛𝑛], incident to an edge with length above K. Now we will show that the length of the edge (x, y) decreases exactly by 1. If A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs 76 not, then denoting = 𝜑𝜑𝑖𝑖−1 −1 (𝜑𝜑𝑖𝑖−1(𝑥𝑥) + 1) , we will have 𝑥𝑥 ⊂̇ 𝑢𝑢. By definition u doesn’t have adjacent vertices in 𝑋𝑋𝜑𝜑𝑖𝑖−1[𝜑𝜑𝑖𝑖−1(𝑦𝑦) + 1, 𝑛𝑛]. Let j be the greatest number, for which 𝜑𝜑𝑗𝑗(𝑢𝑢) < 𝜑𝜑𝑗𝑗(𝑥𝑥) and 𝜑𝜑𝑗𝑗+1(𝑢𝑢) > 𝜑𝜑𝑗𝑗+1(𝑥𝑥). It is clear that j ≤ i-2. In the sub-step j+1 some set U swaps with {x}, where uϵU, at that there exists a vertex v, which is not adjacent to x, but is adjacent to all vertices from U, and therefore, vϵ𝑋𝑋𝜑𝜑𝑖𝑖−1[𝜑𝜑𝑖𝑖−1(𝑦𝑦) + 1, 𝑛𝑛]. Obtained contradiction proves the lemma. Lemma 3: Let vertices 𝑎𝑎 and 𝑏𝑏 satisfy the conditions: 𝜑𝜑𝑖𝑖(𝑎𝑎) < 𝜑𝜑𝑖𝑖(𝑏𝑏) and 𝜑𝜑0(𝑎𝑎) > 𝜑𝜑0(𝑏𝑏). (1) Then there are vertices 𝐷𝐷 and 𝑑𝑑, such that: 𝐷𝐷𝐷𝐷𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑎𝑎) + 1, 𝜑𝜑𝑖𝑖(𝑏𝑏)] and 𝜑𝜑𝑖𝑖(𝑑𝑑) − 𝜑𝜑𝑖𝑖(𝐷𝐷) ≥ 𝐾𝐾, (2) Proof: We will prove the statement by induction. For 𝑖𝑖 = 0 the statement obviously is true, let it is true from 1 to i-1 step inclusive. Consider the step i. Denote 𝑀𝑀1 = 𝑋𝑋𝜑𝜑𝑖𝑖−1[1, 𝜑𝜑𝑖𝑖−1(𝑥𝑥) − 1] and 𝑀𝑀2 = 𝑋𝑋𝜑𝜑𝑖𝑖−1[𝜑𝜑𝑖𝑖−1(𝑧𝑧) + 1, 𝑛𝑛]. We will show, that if for some vertices 𝑎𝑎 and 𝑏𝑏 conditions (1) are fulfilled, then there should exist vertices D’ and d’ which satisfy the conditions (2). The only possible case, when 𝜑𝜑𝑖𝑖−1(𝑎𝑎) > 𝜑𝜑𝑖𝑖−1(𝑏𝑏) can hold when a = z and bϵM. In this case vertices x and y can be taken instead of 𝐷𝐷 and 𝑑𝑑. Really, any vertex from 𝑀𝑀 is adjacent to 𝑑𝑑 = 𝑦𝑦 and 𝜑𝜑𝑖𝑖(𝑑𝑑) − 𝜑𝜑𝑖𝑖(𝐷𝐷) = 𝜑𝜑𝑖𝑖(𝑦𝑦) − 𝜑𝜑𝑖𝑖(𝑥𝑥) ≥ 𝐾𝐾. In other cases 𝜑𝜑𝑖𝑖−1(𝑎𝑎) < 𝜑𝜑𝑖𝑖−1(𝑏𝑏). Let’s analyze possible cases. Case 1. 𝑏𝑏𝐷𝐷𝑀𝑀1. Then 𝑎𝑎𝐷𝐷𝑀𝑀1. Since at the step 𝑖𝑖 only the numbers of vertices from 𝑀𝑀 ∪ {𝑧𝑧} can be changed, then at d’𝐷𝐷𝑀𝑀1 ∪ 𝑀𝑀2 taking 𝐷𝐷 = 𝐷𝐷′ and 𝑑𝑑 = 𝑑𝑑′, it is easy to see that for 𝐷𝐷 and 𝑑𝑑 at 𝜑𝜑𝑖𝑖 conditions (2) are fulfilled. If 𝑑𝑑′ = 𝑧𝑧, then from the fact that 𝑧𝑧 ⊂̇ 𝑞𝑞 for any 𝑞𝑞ϵM, it follows that each vertex from 𝑋𝑋𝜑𝜑𝑖𝑖−1[𝜑𝜑𝑖𝑖−1(𝐷𝐷 ′), 𝜑𝜑𝑖𝑖−1(𝑏𝑏)] is adjacent to each vertex from M. Note that some vertex from M receives the number 𝜑𝜑𝑖𝑖−1(𝑧𝑧) at 𝜑𝜑𝑖𝑖. Then taking 𝐷𝐷 = 𝐷𝐷′ and 𝑑𝑑 = 𝜑𝜑𝑖𝑖 −1�𝜑𝜑𝑖𝑖−1(𝑧𝑧)�, one can observe, that for 𝐷𝐷 and 𝑑𝑑 conditions (2) will be fulfilled. If d’ϵM, then as 𝜑𝜑𝑖𝑖(𝑞𝑞) ≥ 𝜑𝜑𝑖𝑖−1(𝑞𝑞) for each 𝑞𝑞ϵM, we will have 𝜑𝜑𝑖𝑖(d’) − 𝜑𝜑𝑖𝑖(𝐷𝐷′) ≥ 𝜑𝜑𝑖𝑖−1(d’) − 𝜑𝜑𝑖𝑖−1(𝐷𝐷′) and we can take 𝐷𝐷 = 𝐷𝐷′ and 𝑑𝑑 = 𝑑𝑑′ Case 2. 𝑏𝑏 = 𝑧𝑧. Then 𝑎𝑎𝐷𝐷𝑀𝑀1. If 𝐷𝐷′ ∈ 𝑀𝑀1, then we will put 𝐷𝐷 = 𝐷𝐷′ and 𝑑𝑑 = 𝑑𝑑′, and if 𝐷𝐷′ ∈ 𝑀𝑀, then 𝐷𝐷 = 𝑏𝑏 = 𝑧𝑧 and 𝑑𝑑 = 𝑑𝑑′. Then from the fact that 𝑧𝑧 ⊂̇ 𝑞𝑞 for each 𝑞𝑞 ∈ 𝑀𝑀, it follows that for 𝐷𝐷 and 𝑑𝑑 at 𝜑𝜑𝑖𝑖 conditions (2) are fulfilled. Case 3. 𝑏𝑏 ∈ 𝑀𝑀 ∪ 𝑀𝑀1. At first let’s assume that for any vertex from 𝑋𝑋𝜑𝜑𝑖𝑖−1[𝜑𝜑𝑖𝑖−1(x), 𝜑𝜑𝑖𝑖−1(𝑏𝑏) − 1] occurs 𝜑𝜑0(𝑞𝑞) < 𝜑𝜑0(𝑏𝑏). Then 𝑎𝑎𝐷𝐷𝑀𝑀1. If 𝑏𝑏 ∈ 𝑀𝑀, then in place of 𝐷𝐷 one can take the vertex 𝑥𝑥 and in place of 𝑑𝑑 – vertex 𝑦𝑦, i.e., all vertices from 𝑀𝑀 are adjacent to 𝑦𝑦. If 𝑏𝑏 ∈ 𝑀𝑀2 and 𝐷𝐷′ ∈ 𝑀𝑀2, then during the transition from 𝜑𝜑𝑖𝑖−1 to 𝜑𝜑𝑖𝑖, nothing is changed for a and b, therefore we can take 𝐷𝐷 = 𝐷𝐷′ and 𝑑𝑑 = 𝑑𝑑′. Let 𝑏𝑏 ∈ 𝑀𝑀2 and 𝐷𝐷′ ∈ 𝑀𝑀. Since 𝑧𝑧 is adjacent to 𝑑𝑑′, then all vertices from 𝑀𝑀 will be adjacent to 𝑑𝑑′, and one can take 𝐷𝐷 = 𝑧𝑧 (certainly only after receiving the number 𝜑𝜑𝑖𝑖−1(x) by z) and 𝐷𝐷 = 𝐷𝐷′. Now let q be a vertex from 𝑋𝑋𝜑𝜑𝑖𝑖−1[𝜑𝜑𝑖𝑖−1(x), 𝜑𝜑𝑖𝑖−1(𝑏𝑏) − 1], the index of which is greater than the index of b, and let c be the vertex with the greatest number among them at 𝜑𝜑𝑖𝑖−1. Let 𝑏𝑏 ∈ 𝑀𝑀2. Then ∈ 𝑀𝑀2 ∪ {𝑧𝑧} . Really, if 𝑐𝑐 ∈ 𝑀𝑀, then from 𝑧𝑧 ⊂̇ 𝑐𝑐 we will have 𝜑𝜑0(𝑧𝑧) > 𝜑𝜑0(𝑐𝑐) and therefore – 𝜑𝜑0(𝑧𝑧) > 𝜑𝜑0(𝑏𝑏), which will be at odds with the selection of c. But if cϵM2∪{z}, then at 𝜑𝜑𝑖𝑖−1 there are 𝐷𝐷′ and 𝑑𝑑′, satisfying (2), at that 𝐷𝐷′ ∈ 𝑀𝑀2, and as their D. Muradian 77 numbers are not changed during the transition from 𝜑𝜑𝑖𝑖−1 to 𝜑𝜑𝑖𝑖, then one can take 𝐷𝐷 = 𝐷𝐷′ and 𝑑𝑑 = 𝑑𝑑′. Let 𝑏𝑏 ∈ 𝑀𝑀. If 𝑎𝑎 ∈ 𝑀𝑀1, then one can take 𝐷𝐷 = 𝑥𝑥 and 𝑑𝑑 = 𝑦𝑦. Let 𝑎𝑎 ∈ 𝑀𝑀. Let’s analyze the step 𝑖𝑖. The inequality 𝜑𝜑𝑖𝑖(𝑎𝑎) < 𝜑𝜑𝑖𝑖(𝑏𝑏) means that at 𝜑𝜑𝑖𝑖−1 there was a vertex c’, such that 𝜑𝜑𝑖𝑖−1(𝑎𝑎) < 𝜑𝜑𝑖𝑖−1(c’) < 𝜑𝜑𝑖𝑖−1(𝑏𝑏), whereas at 𝜑𝜑𝑖𝑖 : 𝜑𝜑𝑖𝑖(c’) > 𝜑𝜑𝑖𝑖(𝑏𝑏) , i.e., the vertex was belonging to some nonempty set Sr, and c’ = ar. Therefore, considering the pair of vertices (c’, b) at 𝜑𝜑𝑖𝑖−1, by the inductive conjecture there are vertices 𝐷𝐷′ and 𝑑𝑑′, satisfying (2), the numbers of which are not changed during the transition from 𝜑𝜑𝑖𝑖−1 to 𝜑𝜑𝑖𝑖, i.e., one can take 𝐷𝐷 = 𝐷𝐷′ and 𝑑𝑑 = 𝑑𝑑′. This proves the lemma. Before proving that the algorithm stops without creating a layout with the bandwidth 𝐾𝐾 only on graphs having the bandwidth above 𝐾𝐾, we will define a graph called a generalized 1- caterpillar. Definition: Let 𝐴𝐴𝑖𝑖,𝑉𝑉𝑖𝑖 (𝑖𝑖 ∈ 1, 𝑚𝑚������) be disjoint sets and Ai ≠ ∅ for all (𝑖𝑖 ∈ 1, 𝑚𝑚)�������. A graph H = (F,E) with the set of vertices 𝐹𝐹 = ⋃ 𝐴𝐴𝑖𝑖 ∪ ⋃ 𝑉𝑉𝑖𝑖 𝑚𝑚 𝑖𝑖=1 𝑚𝑚 𝑖𝑖=1 is called a generalized 1-caterpillar if (x,y)ϵE if and only if 𝑥𝑥 ∈ 𝑉𝑉𝑖𝑖, 𝑦𝑦 ∈ 𝐴𝐴𝑖𝑖 (𝑖𝑖 ∈ 1, 𝑚𝑚������), or 𝑥𝑥 ∈ 𝐴𝐴𝑖𝑖 , 𝑥𝑥 ∈ 𝐴𝐴𝑖𝑖+1 (𝑖𝑖 ∈ 1, 𝑚𝑚 − 1�����������), or 𝑥𝑥, 𝑦𝑦 ∈ 𝐴𝐴𝑖𝑖 (𝑖𝑖 ∈ 1, 𝑚𝑚������). Lemma 4: If the number of vertices of the graph H is more than (𝑚𝑚 + 1)(𝐾𝐾 + 1) − ∑ 𝐴𝐴𝑖𝑖 𝑚𝑚 𝑖𝑖=1 , then B(H) > K. Proof: Let 𝑝𝑝 be the number of vertices of 𝐻𝐻 and 𝑝𝑝 > (𝑚𝑚 + 1)(𝐾𝐾 + 1) − ∑ 𝐴𝐴𝑖𝑖 𝑚𝑚 𝑖𝑖=1 . Let’s assume that B(H) ≤ K. Let 𝜑𝜑 be a layout with the smallest bandwidth for H, and without losing generality, let’s assume that 𝜑𝜑−1(1) ∈ 𝐴𝐴𝑖𝑖 ∪ 𝑉𝑉𝑖𝑖 and 𝜑𝜑−1(𝑝𝑝) ∈ 𝐴𝐴𝑗𝑗 ∪ 𝑉𝑉𝑗𝑗 at some 𝑖𝑖, 𝑗𝑗 (1 ≤ i ≤ j ≤ m). Using the assumption B(H) ≤ K, it is easy to prove the following statement: if 𝑧𝑧1𝐷𝐷𝐴𝐴𝑡𝑡 for some t, and 𝑧𝑧2 – vertex from 𝐴𝐴𝑡𝑡+1 with the smallest number, then 𝜑𝜑(𝑧𝑧2) ≤ 𝜑𝜑(𝑧𝑧1) + 𝐾𝐾 − |𝐴𝐴𝑡𝑡+1| + 1. Solving this recurrent inequalities we will obtain that if z is a vertex from 𝐴𝐴𝑗𝑗 with the smallest number, then 𝜑𝜑(𝑧𝑧) ≤ (𝑗𝑗 − 𝑖𝑖 + 1)(𝐾𝐾 + 1) − ∑ |𝐴𝐴𝑡𝑡| 𝑗𝑗 𝑡𝑡=𝑖𝑖 + 1. But z is adjacent to 𝜑𝜑 −1(𝑝𝑝), therefore 𝐾𝐾 ≥ 𝑝𝑝 − 𝜑𝜑(𝑧𝑧) > (𝑚𝑚 + 1)(𝐾𝐾 + 1) − �|𝐴𝐴𝑡𝑡| 𝑚𝑚 𝑡𝑡=1 − (𝑗𝑗 − 𝑖𝑖 + 1)(𝐾𝐾 + 1) + �|𝐴𝐴𝑡𝑡| = 𝑗𝑗 𝑡𝑡=𝑖𝑖 (𝑚𝑚 − 𝑗𝑗 + 𝑖𝑖)(𝐾𝐾 + 1) − �|𝐴𝐴𝑡𝑡| 𝑖𝑖−1 𝑡𝑡=1 − � |𝐴𝐴𝑡𝑡| 𝑚𝑚 𝑡𝑡=𝑗𝑗+1 − 1. Besides |𝐴𝐴𝑡𝑡| ≤ 𝐾𝐾 + 1 for all t ϵ1, 𝑚𝑚������, therefore: 𝐾𝐾 ≥ 𝑝𝑝 − 𝜑𝜑(𝑧𝑧) > (𝑚𝑚 − 𝑗𝑗 + 𝑖𝑖)(𝐾𝐾 + 1) − (𝑚𝑚 − 𝑗𝑗 + 𝑖𝑖 − 1)(𝐾𝐾 + 1) − 1 = 𝐾𝐾, which leads to a contradiction. This proves the lemma. Now we will state the last necessary property of layouts from Φ0. Lemma 5: Let 𝜑𝜑𝐷𝐷𝛷𝛷0 and let 𝑢𝑢1, 𝑢𝑢2, 𝑢𝑢3 be vertices with the following properties: 𝜑𝜑(𝑢𝑢1) < 𝜑𝜑(𝑢𝑢2) < 𝜑𝜑(𝑢𝑢3), (𝑢𝑢1, 𝑢𝑢3)𝐷𝐷𝑈𝑈 and 𝜑𝜑0(𝑢𝑢2) < 𝜑𝜑0(𝑢𝑢3). Then (𝑢𝑢1, 𝑢𝑢2)𝐷𝐷𝑈𝑈. Proof: Let’s assume that 𝑢𝑢1, 𝑢𝑢2 are not adjacent. Then from 𝜑𝜑(𝑢𝑢1) < 𝜑𝜑(𝑢𝑢2) we will have 𝜑𝜑0(𝑢𝑢1) < 𝜑𝜑0(𝑢𝑢2). But (𝑢𝑢1, 𝑢𝑢3)𝐷𝐷𝑈𝑈 and therefore 𝛤𝛤−(𝑢𝑢3�) ⊂ 𝛤𝛤−(𝑢𝑢3�) and 𝜑𝜑0(𝑢𝑢3) < 𝜑𝜑0(𝑢𝑢2), which contradicts the conditions of the lemma. This proves the lemma. Theorem: If the algorithm at some step stops without creating for the graph G a layout with bandwidth K, then B(G) > K. A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs 78 Proof: Let’s assume that the situation described in the formulation of the theorem occurs at step i+1: each vertex from 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑥𝑥), 𝜑𝜑𝑖𝑖(𝑦𝑦)] is adjacent to y. If there is no any vertex among them, the index of which is greater than 𝜑𝜑0(𝑦𝑦), then by Lemma 5, the subgraph induced by the set 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑥𝑥), 𝜑𝜑𝑖𝑖(𝑦𝑦)] is a clique with the vertex number over K+1 and therefore B(G) > K. Let’s assume that there is a vertex in 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑥𝑥), 𝜑𝜑𝑖𝑖(𝑦𝑦) − 1], the index of which is greater than 𝜑𝜑0(𝑦𝑦) and let а1 have the greatest number among them. Denote 𝑏𝑏1 = 𝑦𝑦. Then for а1 and 𝑏𝑏1conditions (1) are fulfilled and therefore there exist vertices D1 from 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(а1) + 1, 𝜑𝜑𝑖𝑖(𝑏𝑏1)] and 𝑏𝑏2 , such that 𝜑𝜑𝑖𝑖(𝑏𝑏2) − 𝜑𝜑𝑖𝑖(𝐷𝐷1) ≥ 𝐾𝐾 and all vertices from 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝐷𝐷1), 𝜑𝜑𝑖𝑖(𝑏𝑏1)] are adjacent to 𝑏𝑏2. Denote 𝑅𝑅0 = 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑥𝑥), 𝜑𝜑𝑖𝑖(𝐷𝐷1) − 1] and 𝐴𝐴1 = 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝐷𝐷1), 𝜑𝜑𝑖𝑖(𝑏𝑏1)]. Then let 𝑎𝑎2 be the vertex with the greatest number from 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑏𝑏1) + 1, 𝜑𝜑𝑖𝑖(𝑏𝑏2)], the index of which is equal or greater than 𝜑𝜑0(𝑏𝑏2) (equality of indices is understood as a simple coincidence: 𝑎𝑎2 = 𝑏𝑏2). Let 𝑎𝑎2 ≠ 𝑏𝑏2. Then 𝑎𝑎2, 𝑏𝑏2 satisfy the conditions (1) and therefore there exist vertices D2 from 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(а2) + 1, 𝜑𝜑𝑖𝑖(𝑏𝑏2)] and 𝑏𝑏3, for which the conditions (2) are fulfilled (after taking 𝐷𝐷 = 𝐷𝐷1, 𝑑𝑑 = 𝑏𝑏3 in (2)). Denote 𝑅𝑅1 = 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝑏𝑏1) + 1, 𝜑𝜑𝑖𝑖(𝐷𝐷2) − 1] and 𝐴𝐴2 = 𝑋𝑋𝜑𝜑𝑖𝑖[𝜑𝜑𝑖𝑖(𝐷𝐷2), 𝜑𝜑𝑖𝑖(𝑏𝑏2)]. Let’s continue this procedure. As the graph is finite, then the sets 𝐴𝐴1, 𝐴𝐴2, … , 𝐴𝐴𝑚𝑚 and 𝑅𝑅0, 𝑅𝑅1, … , 𝑅𝑅𝑚𝑚 will be obtained, such that 𝑅𝑅𝑗𝑗 = 𝑋𝑋𝜑𝜑𝑖𝑖�𝜑𝜑𝑖𝑖�𝑏𝑏𝑗𝑗� + 1, 𝜑𝜑𝑖𝑖�𝐷𝐷𝑗𝑗+1� − 1� 𝑎𝑎𝑎𝑎 𝑚𝑚 ≥ 1, 𝐴𝐴𝑗𝑗 = 𝑋𝑋𝜑𝜑𝑖𝑖�𝜑𝜑𝑖𝑖�𝐷𝐷𝑗𝑗�, 𝜑𝜑𝑖𝑖�𝑏𝑏𝑗𝑗�� 𝑎𝑎𝑎𝑎 j ϵ1, 𝑚𝑚������, at that 𝜑𝜑𝑖𝑖�𝑏𝑏𝑗𝑗� − 𝜑𝜑𝑖𝑖�𝐷𝐷𝑗𝑗−1� ≥ 𝐾𝐾 (j ϵ1, 𝑚𝑚 + 1�����������, 𝐷𝐷0 = 𝑥𝑥), every vertex from 𝐴𝐴𝑗𝑗 is adjacent to 𝑏𝑏𝑗𝑗+1 (j ϵ1, 𝑚𝑚������), every vertex from 𝑅𝑅0 is adjacent to 𝑏𝑏1 and there are no vertices in 𝑅𝑅0 , the indices of which are above 𝜑𝜑0(𝑏𝑏𝑚𝑚+1). From Lemma 5 we know that every vertex from 𝑅𝑅0 is adjacent to every vertex from 𝐴𝐴1, every vertex from 𝐴𝐴𝑗𝑗 is adjacent to every vertex from 𝐴𝐴𝑗𝑗+1 (j ϵ1, 𝑚𝑚 − 1�����������) and every vertex from 𝐴𝐴𝑚𝑚 is adjacent to every vertex from 𝑅𝑅𝑚𝑚. Let u be an arbitrary vertex from 𝑅𝑅𝑗𝑗 (j ϵ1, 𝑚𝑚 − 1�����������). We will show, that if u is not adjacent to any vertex from 𝐴𝐴𝑗𝑗 (𝐴𝐴𝑗𝑗+1), then it is adjacent to all vertices from 𝐴𝐴𝑗𝑗+1 (correspondingly: 𝐴𝐴𝑗𝑗), where j ϵ1, 𝑚𝑚 − 1�����������). Really, assume the contrary: 𝑢𝑢1𝐷𝐷А𝑗𝑗, 𝑢𝑢2𝐷𝐷А𝑗𝑗+1 and both are adjacent to u. From 𝜑𝜑𝑖𝑖(𝑢𝑢) < 𝜑𝜑𝑖𝑖(𝑢𝑢2) we have 𝜑𝜑0(𝑢𝑢) < 𝜑𝜑0(𝑢𝑢2). Then applying Lemma 5 to the triple 𝑢𝑢1, 𝑢𝑢2, 𝑢𝑢3, we will get that 𝑢𝑢1 is adjacent to 𝑢𝑢, which leads to a contradiction. Therefore every vertex 𝑢𝑢ϵ𝑅𝑅𝑗𝑗 (j ϵ1, 𝑚𝑚 − 1�����������) is adjacent to all vertices of at least one of the sets 𝐴𝐴𝑗𝑗, 𝐴𝐴𝑗𝑗+1. Let 𝑉𝑉1 be a set consisting of all vertices of 𝑅𝑅0 and those vertices from 𝑅𝑅1, which are adjacent to all vertices of 𝐴𝐴1. Let 𝑉𝑉𝑗𝑗 be a set consisting of all vertices of 𝑅𝑅𝑗𝑗−1\𝑉𝑉𝑗𝑗−1 and those vertices from 𝑅𝑅𝑗𝑗, which are adjacent to all vertices of 𝐴𝐴𝑗𝑗 (j ϵ1, 𝑚𝑚 − 1�����������), and 𝑉𝑉𝑚𝑚 = (𝑅𝑅𝑚𝑚−1\𝑉𝑉𝑚𝑚−1) ∪ 𝑅𝑅𝑚𝑚. It is easy to see that the graph G contains as a subgraph a generalized 1-caterpillar satisfying the conditions of Lemma 4. This proves the theorem. 5. Estimation of Algorithm Complexity From the definition of 𝜑𝜑0 and its second property we have 𝐵𝐵𝜑𝜑0(𝐺𝐺) ≤ ∆ − 1, where ∆ is the maximal degree of vertices. On the other hand we have a trivial lower bound: 𝐵𝐵𝜑𝜑0(𝐺𝐺) ≥ 𝐵𝐵(𝐺𝐺) ≥ � ∆ 2 � . Therefore �∆ 2 � ≤ 𝐵𝐵(𝐺𝐺) ≤ ∆ − 1. First we will estimate the running time of the step i. The vertex z can be found checking |𝑀𝑀| vertices and |𝑀𝑀| elementary operations are sufficient for the swap of sets (𝑀𝑀, {𝑧𝑧}) (for the assignment of numbers). The rest part of the step i, i.e., the problem of finding vertices 𝑎𝑎𝑗𝑗 as well as realization of swaps ({𝑎𝑎𝑗𝑗}, 𝑆𝑆𝑗𝑗) is equivalent to one pass of known bubble algorithm, and D. Muradian 79 therefore will require no more than |𝑀𝑀| comparisons of indices and |𝑀𝑀| operations for the reassignments of numbers. Therefore the step i will require O(|𝑀𝑀|) elementary operations. As the vertex set 𝑀𝑀 forms a clique (the corresponding intervals contain the interval �̂�𝑧), then |𝑀𝑀| ≤ 𝐾𝐾 + 1. Besides the length of the edge (x, y) no more than 2𝐾𝐾, because �∆ 2 � ≤ 𝐾𝐾 ≤ ∆ − 1. So, in order to decrease the length of the edge (𝑥𝑥, 𝑦𝑦) to 𝐾𝐾 no more than 𝐾𝐾 steps are needed. Therefore, to achieve a situation where 𝑦𝑦 is not adjacent to an edge with length over 𝐾𝐾, 𝑂𝑂(𝐾𝐾2) elementary operations are sufficient. Finally, due to the fact that �∆ 2 � ≤ 𝐾𝐾 ≤ ∆ − 1, the bandwidth minimization problem for an interval graph with number of vertices n and with maximal vertex degree ∆, can be solved using 𝑂𝑂(∆2𝑛𝑛 log2 ∆) elementary operations. References [1] L. H. Harper, “Optimal numberings and isoperimetric problems on graphs”, Journal of Combinatorial Theory, vol.1, no. 3, pp. 385–393, 1966. [2] C. Papadimitriou, “The NP-completeness of the bandwidth minimization problem”, Computing, vol. 16, pp. 263-270, 1976. [3] D. Muradian, “The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete”, Theoretical Computer Science, “Selected Papers in Honour of Lawrence Harper”, vol. 307, no. 3, pp. 567-572, 2003. [4] Y.-L. Lai, Bandwidth, edgesum and profile of graphs. Ph.D. thesis, Dept. of Computer Science, Western Michigan Univ, 1997. [5] T. Kloks, D. Kratsch and H. Muller, “Bandwidth of chain graphs”, Information Processing Letters, vol. 68, no. 6, pp. 313-315, 1998. [6] S. F. Assman, Peck et al., “The bandwidth of caterpillars with hair of length 1 and 2”, SIAM Journal on Algebraic and Discrete Methods, vol. 2, pp. 387-393, 1981. [7] Д. О. Мурадян, “Полиномиальный алгоритм для нахождения минимаксных нумераций графов интервалов”, Академия Наук Арм. ССР, в. 82, pp. 64-66, 1986. [8] D. Kleitman and R. Vohra, “Computing the bandwidth of interval graphs”, SIAM J. Discrete Math., vol. 3, no. 3, pp. 373-375, 1990. [9] R. Mahesh, C. P. Rangan and A. Srinivasan, “On finding the minimum bandwidth of interval graphs”, Information and Computation, vol. 95, no. 2, pp. 218-224, 1991. [10] A. P Sprague, “An O(n log n) algoritm for bandwidth of interval graphs”, SIAM Journal on Discrete Mathematics, vol. 7, no. 2, pp. 213-220, 1994. Submitted 21.07.2016, accepted 24.10.2016. http://dblp.uni-trier.de/db/journals/siamdm/siamdm3.html%23KleitmanV90 http://dblp.uni-trier.de/db/journals/siamdm/siamdm3.html%23KleitmanV90 A Polynomial Algorithm for the Minimum Bandwidth of Interval Graphs 80 Պոլինոմիալ բարդությամբ ալգորիթմ ինտերվալ գրաֆների բարձրությունը գտնելու համար Դ. Մուրադյան Ամփոփում Դիցուք G-ն կապակցված գրաֆ է X գագաթների և U կողերի բարձրությամբ: Յուրաքանչյուր փոխմիարժեք 𝜑𝜑 համապատասխանություն, որ գագաթների X բազմությունը արտապատկերում է {1, 2, . . . , |X|} բազմության վրա, կոչվում է G գրաֆի համարակալում: 𝐵𝐵𝜑𝜑(𝐺𝐺) = max | 𝜑𝜑(𝑢𝑢) − 𝜑𝜑(𝑣𝑣)| թիվը, որտեղ մաքսիմումը վերցվում է ըստ գրաֆի բոլոր կողերի, սահմանվում է որպես 𝜑𝜑 համարակալման բարձրություն: G գրաֆի բարձրությունը սահմանվում է որպես B(G) = min𝐵𝐵𝜑𝜑(𝐺𝐺), որտեղ մինիմումը վերցվում է ըստ գրաֆի բոլոր համարակալումների: Ինտերվալ գրաֆը սահմանվում է որպես թվային առանցքի վրա տրված ինտերվալների ինչ-որ ընտանիքի հատումների գրաֆ: Աշխատանքում բերվում է ինտերվալ գրաֆների բարձրությունը գտնող պոլինոմիալ բարդությամբ ալգորիթմ: Ալգորիթմն ունի O�n∆2log(∆)� բարդություն, որտեղ n-ը գրաֆի գագաթների քանակն է, իսկ Δ-ն՝ գագաթների մեծագույն աստիճանը: Алгоритм полиномиальной сложности для нахождения высоты графов интервалов Д. Мурадян Аннотация Пусть G=(X, U) – граф со множеством вершин X и ребер U. Каждое взаимно- однозначное отображение { }|X| , ,2 ,1: →Xϕ назовем его нумерацией. При этом число |𝜑𝜑(𝑥𝑥) − 𝜑𝜑(𝑦𝑦)| назовем длиной ребра (x,y), а числа 𝐵𝐵𝜑𝜑(𝐺𝐺) = max(𝑥𝑥,𝑦𝑦)∈𝑈𝑈 |𝜑𝜑(𝑥𝑥) − 𝜑𝜑(𝑦𝑦)| и 𝐵𝐵(𝐺𝐺) = min 𝜑𝜑 𝐵𝐵𝜑𝜑(𝐺𝐺), где минимум берется по всевозможным нумерациям графа G, соответственно - высотой нумерации 𝜑𝜑 и графа G. Граф интервалов определяется как граф пересечений семейства интервалов данных на числовой прямой. В настоящей работе приводится алгоритм полиномиальной сложности для нахождения высоты произвольного графа интервалов. Алгоритм имеет сложность O�n∆2log(∆)�, где n – количество вершин, а Δ – максимальная степень вершин графа. 1. Introduction 2. Preliminaries 3. Algorithm 4. Proof of the Algorithm’s Correctness 5. Estimation of Algorithm Complexity